Domande e Risposte - Calcolatori Elettronici A.A. 2024-2025

Indice

Note per lo Studio

1. Architettura di Base e Memoria

Domanda 1.1 (answered)

Domanda: Nell’architettura CPU-Memoria-I/O che stiamo studiando, chi conosce cosa? Spieghi dettagliatamente la conoscenza e ignoranza di ciascun componente del sistema.

Risposta: Nell’architettura classica CPU-Memoria-I/O, ogni componente ha una visione parziale del sistema, fondamentale per la separazione dei compiti e la sicurezza.

CPU:

La CPU conosce solo i propri registri interni e può accedere alla memoria tramite indirizzi, ma non ha conoscenza diretta della struttura fisica della RAM o delle periferiche. La CPU invia segnali di lettura/scrittura e indirizzi, ma non “vede” cosa c’è oltre l’interfaccia di memoria.

Memoria (RAM):

La memoria è un dispositivo passivo: non conosce la CPU né le periferiche. Si limita a rispondere alle richieste di lettura/scrittura sugli indirizzi che le vengono forniti. Non ha consapevolezza di chi stia accedendo o del significato dei dati.

Periferiche/I/O:

Le periferiche sono progettate per rispondere a comandi specifici, ma non conoscono la CPU o la RAM. Interagiscono tramite registri di controllo e dati, e possono generare segnali di interruzione per notificare eventi alla CPU.

Riferimento:

“La CPU comunica con la memoria e le periferiche tramite bus dedicati. Ogni componente è progettato per ignorare i dettagli interni degli altri, garantendo modularità e sicurezza.”

Fonte: Memoria e Periferiche.md

Esempio pratico:

Quando la CPU esegue un’istruzione di scrittura, invia un indirizzo e un dato sul bus. La RAM riceve la richiesta e memorizza il dato, senza sapere se proviene da un programma utente o dal sistema operativo. Analogamente, una periferica riceve comandi senza sapere chi li ha generati.

Conclusione: Questa architettura a conoscenza limitata permette di realizzare sistemi scalabili, sicuri e facilmente espandibili.

Domanda 1.2 (answered)

Domanda: Come viene gestito il flusso di controllo al momento dell’avvio del calcolatore? Cosa succede quando il contenuto della RAM è casuale?

Risposta: Il flusso di controllo all’avvio del calcolatore è gestito attraverso una sequenza ben definita di passaggi che iniziano dalla ROM e portano all’esecuzione del sistema operativo, gestendo il problema critico del contenuto casuale della RAM.

Il problema del contenuto casuale della RAM:

Problema fondamentale all’avvio:

Al’avvio del calcolatore però il contenuto della memoria RAM è casuale. È quindi necessario che il programma di bootstrap, ovvero quelle informazioni necessarie a inizializzare in maniera corretta l’%rip.

Fonte: Memoria e Periferiche.md

Soluzione tramite ROM e BIOS:

Il programma bootstrap deve essere salvato in una memoria ROM sulla quale il programma deve essere salvato.

All’inizio della storia dei calcolatori il programma di bootstrap veniva caricato manualmente dagli operatori ad ogni accensione del calcolatore. La ROM permette di non dover fare più questa operazione, è infatti sufficente impostare che in fase di /reset la CPU vada a consultare quest’ultima. Il BIOS è contenuto in questa parte di programma.

Fonte: Memoria e Periferiche.md

Sequenza di avvio nei processori Intel:

Modalità di avvio progressive:

I processori intel sono ancora oggi progettati per avviarsi a 16bit in modalità non protetta. Via software vengono poi portati in modalità protetta a 32bit, in generale grazie ad un programma di bootstrap nel BIOS. Nel nostro caso sarà l’emulatore stesso ad effettuare questo primo passaggio.

Tocca a noi però portare il processore nella modalità a 64bit, e questo compito lo facciamo svolgere al programma boot.bin che può cedere il controllo al modulo sistema.

Fonte: Sistemi Multiprocesso e Processi.md

Processo di bootstrap dettagliato:

Il bootloader e il caricamento dei moduli:

Il programma boot.bin esegue una serie di allocazioni in memoria per permettere il corretto funzionamento della nostra macchina.

Le righe 1-15 arrivano dal programma boot.bin:

Fonte: Sistemi Multiprocesso e Processi.md

Esempio concreto della sequenza di avvio: Dal log di avvio del sistema possiamo vedere la sequenza completa:

1 | [INF] - Boot loader di Calcolatori Elettronici, v1.0
2 | [INF] - Memoria totale: 32 MiB, heap: 636 KiB
3 | [INF] - Argomenti: /home/gabrieledc/CE/lib/ce/boot.bin
4 | [INF] - Il boot loader precedente ha caricato 3 moduli:
5 | [INF] - - mod[0]: start=114000 end=12f580 file=build/sistema.strip
6 | [INF] - - mod[1]: start=130000 end=1414e0 file=build/io.strip
7 | [INF] - - mod[2]: start=142000 end=147400 file=build/utente.strip
8 | [INF] - Copio mod[0] agli indirizzi specificati nel file ELF:
9 | [INF] - - copiati 108560 byte da 114000 a 200000
10 | [INF] - - copiati 970 byte da 12edb8 a 21bdb8
11 | [INF] - - azzerati ulteriori 79030 byte
12 | [INF] - - entry point 200178
13 | [INF] - Creata finestra sulla memoria centrale: [ 1000, 2000000)
14 | [INF] - Creata finestra per memory-mapped-IO: [ 2000000, 100000000)
15 | [INF] - Attivo la modalita' a 64 bit e cedo il controllo a mod[0]...

Fonte: Sistemi Multiprocesso e Processi.md

Controllo del flusso di esecuzione:

Principio fondamentale:

Abbiamo più volte detto che la CPU non fa altro che leggere e eseguire le istruzioni una alla volta. Per capire però dove recuperare una nuova istruzione una volta eseguita quella precedente va a consultare l’istruction Pointer %rip che viene aggiornato dell’operazione precedente.

Il controllo è unico e può essere solo scambiato tra i vari stati della CPU, a loro volta scanditi dal programma in esecuzione.

Fonte: Memoria e Periferiche.md

Attivazione della modalità 64-bit: Il passaggio finale alla modalità a 64-bit avviene attraverso la paginazione:

; settiamo il bit 31 di CR0
    MOVl %cr0, %eax
    ORl $0x80010000, %eax    // paging & write-protect
    MOVl %eax, %cr0
; ora la modalità a 64 bit è attiva ...

Fonte: Memoria Virtuale nel Nucleo.md

Gestione della memoria durante l’avvio:

Inizializzazione delle traduzioni di memoria:

Le traduzioni della parte sistema/condivisa sono create dal bootloader prima di abilitare la paginazione tramite la funzione crea_finestra_FM().

La modifica al bootstrap di un processo per creare questa opzione è in realtà abbastanza banale, in quanto all’accensione la MMU è disattivata, e la CPU utilizza direttamente gli indirizzi fisici.

Fonte: Memoria Virtuale nel Nucleo.md e Paginazione.md

Inizializzazione del sistema: Una volta completato il bootstrap, il sistema inizializza i suoi componenti:

Fonte: Sistemi Multiprocesso e Processi.md

In sintesi, il flusso di controllo all’avvio è gestito attraverso una catena di responsabilità: ROM/BIOS → bootloader → boot.bin → modulo sistema, dove ogni componente ha il compito di inizializzare il successivo e trasferirgli il controllo, risolvendo il problema del contenuto casuale della RAM attraverso l’uso di memoria non volatile (ROM) per i programmi di bootstrap.

Domanda 1.3 (answered)

Domanda: Nell’architettura CPU-Memoria-I/O, descriva dettagliatamente come avviene la comunicazione tra CPU e RAM. Cosa sono i segnali /be (Byte Enabler) e come vengono utilizzati nelle operazioni di scrittura?

Risposta: La comunicazione tra CPU e RAM nell’architettura CPU-Memoria-I/O avviene attraverso un sistema di bus strutturato con specifici segnali di controllo, dove i Byte Enabler (/be) svolgono un ruolo cruciale per permettere operazioni selettive sui singoli byte.

Architettura generale CPU-Memoria-I/O:

Struttura fondamentale:

Andremo a studiare un’architettura Architettura CPU - Memoria (RAM e ROM) - I/O. Questa architettura è stata progettata con lo scopo di eseguire software

Fonte: Memoria e Periferiche.md

Struttura del bus di comunicazione:

Composizione del bus CPU-RAM:

CPU e RAM sono collegate da un bus che è composto da:

Fonte: Memoria e Periferiche.md

Interfaccia dei chip di memoria:

Collegamenti del singolo chip di RAM:

Il singolo chip di RAM avrà come collegamenti possibili:

Fonte: Memoria e Periferiche.md

I segnali Byte Enabler (/be):

Definizione e funzione:

Ciò significa che dato un indirizzo A[63:0], il numero di riga verrà identificato dai bit A[63:3]. I restanti A[2:0] rappresentano l’offset all’interno della riga, e vengono chiamati Byte Enabler BE.

Fonte: Memoria e Periferiche.md

Utilizzo nelle operazioni di scrittura: I Byte Enabler permettono di effettuare operazioni selettive sui singoli byte di una riga di memoria, evitando di dover riscrivere l’intera riga quando si vuole modificare solo una parte.

Implementazione hardware dei Byte Enabler:

Collegamento dei chip di memoria: Nell’implementazione hardware, ogni chip di memoria è collegato attraverso un sistema che utilizza i Byte Enabler per determinare quale parte della riga deve essere effettivamente scritta:

assign w_ = W_;
assign r_ = R_;

assign Di = D[8*i + 7 : 8*i];
// Il padding corretto del bus dei dati

assign Ai = A[(k-3)-1 : 0];
/*
* k-3 perché ogni riga di indirizzo contiene 8 indirizzi,
* Se tutti i chip devono memorizzare 2^k byte, ognuno ne memorizzerà:
*   2^k / 8 -> 2^(k-3) byte
* Ciò implica che
*/
wire mask_; assign mask_ = A[n - 1 : n - k] ^ indirizzo_di_riga;
/*
* Metto in OR (sono attivi bassi) :
*  - Il bit corrispettivo del Byte Enabler
*  - XOR tra la parte alta di A e l'indirizzo della riga
*
* Questo si fa per determinare se la regione è quella interpellata
*/
assign s_ = (BE_[i] | mask_);

Fonte: Memoria e Periferiche.md

Esempio di utilizzo nel bus PCI:

Byte Enabler nel contesto PCI: I Byte Enabler sono utilizzati anche in altri contesti sistemici, come nel bus PCI:

BE#[3:0] uscita ingresso Fungono da byte-enabler nelle fasi di trasferimento (BE#[3:0])

Fonte: PCI.md

Caratteristiche delle operazioni di memoria:

Formato delle istruzioni Intel x86:

Il formato delle istruzioni Intelx86 può avere al massimo 1 operando esplicito in memoria.

Tuttavia è possibile operare con due operatori in memoria, attraverso operazioni che hanno accessi impliciti. Alcuni esempi sono la MOVS, PUSH (%rdi), POP(%rdi).

Una qualsiasi informazione che va nella memoria possiede due proprietà:

Fonte: Memoria e Periferiche.md

Dimensioni degli accessi in memoria:

Tipi di accesso supportati:

Nelle memorie per processori Intelx86 che vedremo le dimensioni degli accessi in memoria sono i seguenti:

  B W L Q
Byte 1 2 4 8

Fonte: Memoria e Periferiche.md

Importanza degli allineamenti:

Necessità di accessi multipli per dati non allineati:

Data questa configurazione risulta chiara l’importanza degli allineamenti.

Se volessimo infatti accedere a indirizzi non allineati è necessario fare 2 accessi.

Fonte: Memoria e Periferiche.md

In sintesi, la comunicazione CPU-RAM avviene attraverso un bus strutturato con linee dati, indirizzi e controllo, dove i segnali /be (Byte Enabler) permettono operazioni selettive sui singoli byte, ottimizzando le prestazioni ed evitando riscritture non necessarie di intere righe di memoria. Questo meccanismo è fondamentale per l’efficienza del sistema di memoria e viene implementato a livello hardware attraverso logiche di selezione che determinano quali chip di memoria devono essere attivati per ciascuna operazione.

Domanda 1.4 (answered)

Domanda: Spieghi il problema degli accessi non allineati alla memoria. Come viene gestito dall’hardware il caso di un’operazione MOVQ 4097, %RAX e quale ruolo ha il μ-codice della CPU?

Risposta: Gli accessi non allineati alla memoria rappresentano un problema fondamentale nell’architettura dei calcolatori perché violano il principio di allineamento naturale degli oggetti in memoria.

Allineamento naturale degli oggetti: Un oggetto si dice allineato naturalmente se il suo indirizzo è divisibile per la sua dimensione. Formalmente:

Un oggetto $o$ si dice allineato naturalmente se \(\boxed{|o|_{sizeof(o)} = 0}\)

Fonte: Memoria e Periferiche.md

Tipi di allineamento richiesti:

Organizzazione della memoria RAM:

Nella memoria RAM possiamo identificare una regione come uno spazio di 8Byte. Assegneremo quindi ad ognuna un numero, detto numero di riga, che la identificherà.

Ciò significa che dato un indirizzo A[63:0], il numero di riga verrà identificato dai bit A[63:3]. I restanti A[2:0] rappresentano l’offset all’interno della riga, e vengono chiamati Byte Enabler BE.

Fonte: Memoria e Periferiche.md

Analisi del caso specifico: MOVQ 4097, %RAX: L’operazione MOVQ 4097, %RAX richiede la lettura di 8 byte consecutivi a partire dall’indirizzo 4097.

Scomposizione dell’indirizzo 4097 (0x1001):

Il problema dell’accesso non allineato: Un QUAD (8 bytes) che inizia all’offset 1 si estende fino all’offset 8, ma ogni riga contiene solo gli offset da 0 a 7. Questo significa che i dati richiesti si trovano a cavallo di due righe consecutive.

Gestione hardware:

Data questa configurazione risulta chiara l’importanza degli allineamenti. Se volessimo infatti accedere a indirizzi non allineati è necessario fare 2 accessi.

Fonte: Memoria e Periferiche.md

Processo di gestione hardware:

  1. Primo accesso: Legge la riga 512 per ottenere i byte agli offset 1, 2, 3, 4, 5, 6, 7 (7 bytes)
  2. Secondo accesso: Legge la riga 513 per ottenere il byte all’offset 0 (1 byte rimanente)

Ricomposizione dei dati:

Inoltre potrebbe diventare necessario sistemare il padding dei byte, in quanto quelli all’indirizzo precedente si trovano nella regione delle MSB, anche se per quello che ci riguarda sono nella LSB.

Fonte: Memoria e Periferiche.md

Il ruolo del μ-codice della CPU:

Tutte queste operazioni vengono eseguite non dal software (l’operazione MOVQ 4097, %RAX di fatto fa tutto in una riga), ma dall’hardware, in particolare nel $\mu$-codice che implementa l’accesso in memoria che si trova nella CPU.

Fonte: Memoria e Periferiche.md

Operazioni gestite dal μ-codice:

  1. Rilevare che l’accesso è non allineato
  2. Scomporre l’operazione singola in due accessi separati
  3. Gestire i due accessi alla memoria consecutivi
  4. Ricomporre i dati letti nelle posizioni corrette
  5. Presentare il risultato finale come se fosse stato un singolo accesso

Impatto sulle prestazioni: Gli accessi non allineati hanno un costo significativo perché:

Per questo motivo, i compilatori cercano sempre di allineare naturalmente gli oggetti in memoria, e i programmatori devono prestare attenzione all’allineamento delle strutture dati per ottenere prestazioni ottimali.

2. Memoria Cache

Domanda 2.1 (answered)

Domanda: A che serve la Cache e come funziona? Descriva i principi di funzionamento fondamentali.

Risposta: La memoria cache è una soluzione hardware fondamentale per risolvere il problema della disparità di velocità tra processore e memoria RAM.

Problema che risolve la cache:

La RAM è estrememante lenta rispetto al processore, circa 200/300 volte più lenta, ciò mette in attesa il processore.

Fonte: Memoria e Periferiche.md

Soluzione technologica:

Un modo per avere RAM più veloci è quello di utilizzare le RAM Statiche invece di quelle dinamiche. Le RAM Statiche conservano l’informazione tramite Flip-Flop, e sono realizzabili con 6/7 transistor. Le RAM Dinamiche invece utilizzano microcondensatori che necessitano che l’informazione venga periodicamente “rinfrescata”.

RAM Dinamiche RAM Statiche
Grandi Piccole
Economiche Costose
Lente Veloci

Esiste tuttavia un modo per poter utilizzare RAM grandi, economiche e veloci.

Fonte: Memoria e Periferiche.md

Principi di località: La cache si basa sui principi di località, che sono osservazioni statistiche sul comportamento dei programmi:

Il codice infatti si distribuisce in locazioni di memoria sequenziali, e, statisticamente, raramente effettua salti casuali tra istruzioni. Su questa assunzione di base si fondano i due Principi di Località:

Principio di località Temporale: visto un dato è probabile che molto presto si voglia utilizzare di nuovo.

Principio di località Spaziale: visto un indirizzo è probabile che a breve ci si ritorni.

Fonte: Memoria e Periferiche.md

Funzionamento del controllore cache:

La memoria cache funziona proprio basandosi su questi principi. Infatti quando eseguiamo diversi accessi alla RAM, la cache sarà in ascolto di letture e scritture, salvando in locale i dati che i principi dicono che serviranno.

L’esecuzione della cache è gestita da un controllore che lavora in maniera totalmente trasparente, senza che il processore e il programmatore sappiano della sua esistenza. Tuttavia il programmatore può approfittare dei principi, affinché possa sfruttare al massimo la cache.

Fonte: Memoria e Periferiche.md

Meccanismo di funzionamento:

Il controllore verifica che un dato richiesto dalla CPU sia già stato memorizzato. Se lo è stato lo invia immediatamente, altrimenti effettua una lettura in RAM e lo invia alla CPU. Prima di inviarlo però lo salva localmente, eventualmente rimpiazzando altri dati che erano già salvati. La scelta di quale dato sovrascrivere può essere determinata automaticamente dall’architettura (come nel nostro caso) oppure può utilizzare diversi meccanismi di selezione specifici dell’architettura stessa.

Fonte: Memoria e Periferiche.md

Hit e Miss:

Quando il processore richiede una locazione di memoria, si effettua un controllo per verificare che si trovi o meno nella cache. Il segnale di hit indica che la memoria si trova già nella cache, perciò è sufficente leggere quella.

Il segnale di miss indica invece che la memoria non è nella cache, perciò va recuperato dalla RAM per poter essere letto.

Fonte: Memoria e Periferiche.md

Politiche di scrittura: In caso di scrittura con hit abbiamo due possibili politiche:

Anche in caso di miss la scrittura ha due possibili politiche:

Ottimizzazione per località spaziale:

Il motivo per il quale, data una riga, recuperiamo in cache tutta la sezione dov’è contenuta è perché, per il principio di località, è probabile che il processore richieda in un secondo momento locazioni vicine (località spaziale). Inoltre, se il tempo di lettura di una riga fosse $t$, quella di lettura di un blocco è un tempo $\ll 8t$.

Fonte: Memoria e Periferiche.md

Trasparenza:

La memoria cache lavora solo sulla RAM, non ha alcun senso che lavori per l’I/O, poiché manca il principio base (I/O ha effetti collaterali voluti).

Fonte: Memoria e Periferiche.md

In sintesi, la cache è una memoria piccola, veloce e costosa che funge da buffer intelligente tra CPU e RAM, sfruttando i principi di località per predire quali dati serviranno al processore, migliorando drasticamente le prestazioni del sistema.

Domanda 2.2 (answered)

Domanda: I principi di località valgono sempre? Quando sono rispettati i principi di località?

Risposta: I principi di località non valgono sempre e sono violati in specifici pattern di accesso alla memoria. La loro validità dipende dal tipo di algoritmo e dalla struttura dati utilizzata.

Definizione dei principi di località:

Principi fondamentali:

Il codice infatti si distribuisce in locazioni di memoria sequenziali, e, statisticamente, raramente effettua salti casuali tra istruzioni. Su questa assunzione di base si fondano i due Principi di Località:

Principio di località Temporale: visto un dato è probabile che molto presto si voglia utilizzare di nuovo.

Principio di località Spaziale: visto un indirizzo è probabile che a breve ci si ritorni.

Fonte: Memoria e Periferiche.md

Presupposto statistico:

Infatti, nonostante l’accesso del programmatore alla memoria sia per definizione casuale, ovvero non predeterminato, in realtà nella maggior parte dei casi non lo è realmente.

Fonte: Memoria e Periferiche.md

Quando i principi di località sono rispettati:

1. Codice sequenziale: Il principio di località spaziale è rispettato quando il codice viene eseguito in sequenza, senza salti o chiamate frequenti a funzioni distanti:

Il codice infatti si distribuisce in locazioni di memoria sequenziali, e, statisticamente, raramente effettua salti casuali tra istruzioni.

Fonte: Memoria e Periferiche.md

2. Accessi ad array contigui: Gli accessi sequenziali a array rispettano entrambi i principi:

3. Strutture dati con referenza spaziale: Oggetti e strutture allocate consecutivamente beneficiano della località spaziale:

Il motivo per il quale, data una riga, recuperiamo in cache tutta la sezione dov’è contenuta è perché, per il principio di località, è probabile che il processore richieda in un secondo momento locazioni vicine (località spaziale).

Fonte: Memoria e Periferiche.md

4. Cicli e iterazioni: I loop rispettano il principio di località temporale perché:

Quando i principi di località sono violati:

1. Accessi casuali alla memoria: Pattern di accesso completamente randomici violano entrambi i principi.

2. Conflitti nella cache a indirizzamento diretto:

Questo tipo di cache è particolarmente poco efficente quando cerchiamo di accedere a due cacheline in memoria allineate naturalmente alla dimensione della cache. In questo caso ogni accesso causa una miss, proprio perché i due indirizzi collidono.

Fonte: Memoria e Periferiche.md

3. Strutture dati disperse:

4. Accessi a grandi strutture dati: Quando si accede agli elementi di un array con grandi intervalli (nel nostro caso più grandi di 64Byte), si viola la località spaziale.

5. Operazioni di I/O:

La memoria cache lavora solo sulla RAM, non ha alcun senso che lavori per l’I/O, poiché manca il principio base (I/O ha effetti collaterali voluti).

Fonte: Memoria e Periferiche.md

6. Problemi con cache associative: Anche con cache più sofisticate, i principi possono essere violati:

Tuttavia anche con il registro LRU è possibile generare sempre miss. Basta infatti effettuare un accesso in più di quelli possibili in parallelo, ad esempio se avessimo quattro cache e facessimo l’accesso a 5 linee allineate, genereremmo sempre una miss.

Fonte: Memoria e Periferiche.md

Esempi pratici di violazione:

Pattern di accesso che generano sempre miss: Un esempio concreto è l’accesso a indirizzi che mappano sempre sulla stessa linea di cache:

In particolare, le sezioni che possono fare conflitto in una stessa locazione sono ${\dim{(\mathbf{RAM})} \over \dim{(\mathbf{cache})}}$, ovvero quelle allineate naturalmente a l, con l che indica il numero di cache line disponibili.

Fonte: Memoria e Periferiche.md

Accessi non allineati: Gli accessi non allineati possono causare miss aggiuntivi perché richiedono accessi multipli:

Gli accessi non allineati hanno un costo significativo perché:

Fonte: Domande e Risposte.md

Implicazioni per i programmatori:

Ottimizzazione basata sui principi:

Tuttavia il programmatore può approfittare dei principi, affinché possa sfruttare al massimo la cache.

Fonte: Memoria e Periferiche.md

Strutture dati cache-friendly:

Conclusione: I principi di località sono osservazioni statistiche sui pattern comuni di accesso alla memoria, ma non sono leggi universali. La loro validità dipende dall’algoritmo specifico e dalla struttura dei dati utilizzata. I programmatori consapevoli possono progettare algoritmi e strutture dati che li rispettano per massimizzare l’efficacia della cache, mentre alcuni algoritmi per loro natura li violano sistematicamente.

Domanda 2.3 (answered)

Domanda: Come funziona la cache a indirizzamento diretto? Descriva l’implementazione.

Risposta: La cache a indirizzamento diretto è il tipo più semplice di cache, dove ogni indirizzo di memoria ha una sola posizione possibile nella cache determinata da una funzione matematica.

Principio di funzionamento:

Meccanismo di base:

Il controllore verifica che un dato richiesto dalla CPU sia già stato memorizzato. Se lo è stato lo invia immediatamente, altrimenti effettua una lettura in RAM e lo invia alla CPU. Prima di inviarlo però lo salva localmente, eventualmente rimpiazzando altri dati che erano già salvati.

Fonte: Memoria e Periferiche.md

Scomposizione dell’indirizzo:

La cache divide ogni indirizzo di memoria in tre parti fondamentali:

Ipotizzando che la cache abbia l locazioni, otteniamo che i bit di riga sono gli utlimi k = log(l) (tolti gli ultimi 3 che identificano la riga all’interno del blocco).

Fonte: Memoria e Periferiche.md

Struttura dell’indirizzo in cache:

Implementazione hardware:

Struttura della cacheline:

Le etichette sono quindi grandi n-k-3+2 bit, poiché l’ultimo bit, detto validity, serve per capire se l’etichetta in quella riga è valida o contiene valori casuali, mentre il penultimo, detto dirty, serve per ottimizzare i tempi in caso di scritture in RAM dovute a rimpiazamenti di cacheline.

Fonte: Memoria e Periferiche.md

Campi di ogni entrata del controllore di etichette:

  1. Tag: Identifica quale blocco di memoria è memorizzato
  2. Validity bit (V): Indica se il contenuto della cacheline è valido
  3. Dirty bit (D): Indica se la cacheline è stata modificata rispetto alla RAM

Nella cacheline si hanno i dati effettivi (tipicamente 64 byte)

Algoritmo di funzionamento:

Procedura di accesso in lettura:

  1. Estrazione dell’index: Usa i bit dell’index per selezionare la riga della cache
  2. Confronto del tag: Confronta il tag dell’indirizzo con quello memorizzato nella riga
  3. Controllo validity: Verifica che il bit V sia settato
  4. Hit/Miss decision:
    • Hit: Se tag coincide e V=1, restituisce il dato dalla cache
    • Miss: Se tag non coincide o V=0, accede alla RAM

Gestione degli accessi in scrittura:

Politiche in caso di Hit:

In caso di scrittura con hit abbiamo due possibili politiche:

Fonte: Memoria e Periferiche.md

Politiche in caso di Miss:

Anche in caso di miss la scrittura ha due possibili politiche:

Fonte: Memoria e Periferiche.md

Gestione del dirty bit:

Per migliorare il tempo si aggiunge un’ulteriore bit alle etichette chiamato D (Dirty) che identifica se in una determinata cache-line sono avvenute o meno scritture.

Fonte: Memoria e Periferiche.md

Vantaggi dell’implementazione:

1. Semplicità:

2. Velocità:

3. Ottimizzazione per località spaziale:

Il motivo per il quale, data una riga, recuperiamo in cache tutta la sezione dov’è contenuta è perché, per il principio di località, è probabile che il processore richieda in un secondo momento locazioni vicine (località spaziale). Inoltre, se il tempo di lettura di una riga fosse $t$, quella di lettura di un blocco è un tempo $\ll 8t$.

Fonte: Memoria e Periferiche.md

Limitazioni e problemi:

Conflitti tra indirizzi allineati:

Con questo tipo di cache, detta ad indirizzamento diretto, si possono generare conflitti tra sezioni. In particolare, le sezioni che possono fare conflitto in una stessa locazione sono ${\dim{(\mathbf{RAM})} \over \dim{(\mathbf{cache})}}$, ovvero quelle allineate naturalmente a l, con l che indica il numero di cache line disponibili.

Fonte: Memoria e Periferiche.md

Problema dei conflitti sistematici:

Questo tipo di cache è particolarmente poco efficente quando cerchiamo di accedere a due cacheline in memoria allineate naturalmente alla dimensione della cache. In questo caso ogni accesso causa una miss, proprio perché i due indirizzi collidono.

Fonte: Memoria e Periferiche.md

Esempio pratico di conflitto: Se la cache ha 8 KiB righe (2^13), gli indirizzi 0x0000 e 0x1000 mapperanno sulla stessa riga perché differiscono solo nei bit superiori (tag), ma hanno lo stesso index. Questo causa thrashing quando si accede alternativamente a questi indirizzi.

Ottimizzazioni per le scritture:

Write-back vs Write-through:

Per quanto riguarda la write-back, la scrittura verrà comunque eseguita in RAM prima o poi, nel peggiore dei casi quando quella cache line viene sostituita. Il guadagno del non fare direttamente il write-through si vede quando effettuiamo un numero molto elevato di scritture nella stessa cache-line.

Fonte: Memoria e Periferiche.md

Algoritmo di sostituzione: Nella cache a indirizzamento diretto non c’è scelta: quando serve spazio per una nuova cacheline, quella esistente viene sempre sostituita. Se il dirty bit è settato, viene prima eseguito il write-back in RAM.

Confronto con cache associative:

La soluzione ai problemi di conflitto è rappresentata dalle cache associative:

Un modo per risolvere il problema è attraverso le cache associative ad insiemi.

Fonte: Memoria e Periferiche.md

Collegamenti con altre domande:

Conclusioni: La cache a indirizzamento diretto rappresenta la forma più semplice ed efficiente di cache in termini di hardware, ma soffre di conflitti sistematici che possono degradare le prestazioni in scenari specifici. La sua semplicità la rende ideale per implementazioni dove il costo e la velocità sono prioritari rispetto alla flessibilità.

Domanda 2.4 (answered)

Domanda: Come è fatta una cacheline? Quali informazioni contiene e come viene gestita?

Risposta: Una cacheline è l’unità fondamentale di trasferimento e memorizzazione nella memoria cache, composta da dati effettivi e metadati di controllo che permettono la gestione efficiente delle operazioni di lettura e scrittura.

Struttura di una Cacheline

Componenti Principali

1. Dati effettivi: La cacheline contiene un blocco di dati contigui dalla memoria principale, tipicamente di 64 byte (8 parole da 64 bit). Questo blocco viene recuperato per intero dalla RAM quando si verifica un miss, sfruttando il principio di località spaziale.

Il motivo per il quale, data una riga, recuperiamo in cache tutta la sezione dov’è contenuta è perché, per il principio di località, è probabile che il processore richieda in un secondo momento locazioni vicine (località spaziale). Inoltre, se il tempo di lettura di una riga fosse $t$, quella di lettura di un blocco è un tempo $\ll 8t$.

Fonte: Memoria e Periferiche.md

2. Metadati di controllo (etichette):

Le etichette sono quindi grandi n-k-3+2 bit, poiché l’ultimo bit, detto validity, serve per capire se l’etichetta in quella riga è valida o contiene valori casuali, mentre il penultimo, detto dirty, serve per ottimizzare i tempi in caso di scritture in RAM dovute a rimpiazamenti di cacheline.

Fonte: Memoria e Periferiche.md

Campi di Controllo Dettagliati

1. Tag (n-k-3 bit):

2. Validity Bit (V):

3. Dirty Bit (D):

Per migliorare il tempo si aggiunge un’ulteriore bit alle etichette chiamato D (Dirty) che identifica se in una determinata cache-line sono avvenute o meno scritture.

Fonte: Memoria e Periferiche.md

Gestione delle Cacheline

- Operazioni di Lettura

Procedura di accesso:

  1. Estrazione dell’index: Usa i bit dell’index dell’indirizzo per selezionare la riga
  2. Confronto del tag: Confronta il tag dell’indirizzo con quello memorizzato
  3. Controllo validity: Verifica che V=1
  4. Decisione hit/miss:

Il segnale di hit indica che la memoria si trova già nella cache, perciò è sufficente leggere quella.

Fonte: Memoria e Periferiche.md

- Operazioni di Scrittura

In caso di HIT:

In caso di scrittura con hit abbiamo due possibili politiche:

Fonte: Memoria e Periferiche.md

In caso di MISS:

Anche in caso di miss la scrittura ha due possibili politiche:

Fonte: Memoria e Periferiche.md

- Gestione del Dirty Bit

Write-back ottimizzata:

Per quanto riguarda la write-back, la scrittura verrà comunque eseguita in RAM prima o poi, nel peggiore dei casi quando quella cache line viene sostituita. Il guadagno del non fare direttamente il write-through si vede quando effettuiamo un numero molto elevato di scritture nella stessa cache-line.

Fonte: Memoria e Periferiche.md

Algoritmo di sostituzione: Quando una cacheline dirty deve essere sostituita:

  1. Controllo del dirty bit: Se D=1, esegue write-back in RAM
  2. Invalidazione: Setta V=0
  3. Caricamento: Carica la nuova cacheline dalla RAM
  4. Aggiornamento metadati: Setta nuovo tag, V=1, D=0

- Interazione con DMA

Problemi di coerenza:

In questa politica le scritture della CPU vengono mantenute soltanto in cache e effettuate in maniera sincrona in secondi momenti (come quando la cacheline dirty verrebbe sovrascritta). Le cacheline ~dirty invece continuano a contenere le stesse informazioni della RAM.

Fonte: DMA.md

Soluzioni hardware (Intel):

Se le linee di controllo identificano un operazione di scrittura, il controllore può usare il contenuto delle linee di indirizzo per eseguire una normale ricerca in cache, e nel caso di hit invalidare in autonomia la corrispondente cacheline.

Fonte: DMA.md

Vantaggi della Struttura

1. Efficienza spaziale:

2. Gestione trasparente:

3. Coerenza dei dati:

La cacheline rappresenta quindi un’unità di memorizzazione intelligente che bilancia efficienza, coerenza e semplicità di gestione hardware, costituendo il mattone fondamentale dell’architettura delle memorie cache moderne.

Domanda 2.5 (answered)

Domanda: Descriva le politiche di sostituzione delle cacheline e i loro vantaggi/svantaggi. Spiega LRU e pseudo-LRU.

Risposta: Le politiche di sostituzione delle cacheline determinano quale cacheline rimuovere quando la cache è piena e deve essere caricata una nuova cacheline. La scelta della politica influenza direttamente le prestazioni del sistema.

Contesto del problema:

La scelta di quale dato sovrascrivere può essere determinata automaticamente dall’architettura (come nel nostro caso) oppure può utilizzare diversi meccanismi di selezione specifici dell’architettura stessa.

Fonte: Memoria e Periferiche.md

Differenza tra cache a indirizzamento diretto e associative:

Cache a indirizzamento diretto:

Questo tipo di cache è particolarmente poco efficente quando cerchiamo di accedere a due cacheline in memoria allineate naturalmente alla dimensione della cache. In questo caso ogni accesso causa una miss, proprio perché i due indirizzi collidono.

Fonte: Memoria e Periferiche.md

Cache associative per insiemi:

- POLITICHE DI SOSTITUZIONE

1. LRU (Least Recently Used)

Principio:

Si utilizzano le due cache in parallelo, in caso di conflitti, andremo a sovrascrivere la cacheline che non si utilizza da più tempo.

Fonte: Memoria e Periferiche.md

Implementazione hardware:

Oltre alle cache, si introduce anche un ulteriore registro R che contiene tanti bit quanti sono necessari per ricordare l’ordinamento delle scritture.

In caso di due vie in R è sufficente 1bit, che codifica quale delle due cache non si utilizza da più tempo in quella line. In caso di quattro vie il registro viene chiamato LRU e contiene 5bit.

Fonte: Memoria e Periferiche.md

Vantaggi dell’LRU:

  1. Ottimalità teorica: Approssima il comportamento ottimale per molti pattern di accesso
  2. Sfrutta la località temporale: Mantiene in cache i dati utilizzati più di recente
  3. Prestazioni predibili: Comportamento consistente per pattern sequenziali

Svantaggi dell’LRU:

  1. Complessità hardware: Richiede hardware aggiuntivo per tracciare l’ordine di accesso
  2. Overhead: Ogni accesso deve aggiornare i bit di stato
  3. Non sempre ottimale: Può fallire in pattern specifici

Tuttavia anche con il registro LRU è possibile generare sempre miss. Basta infatti effettuare un accesso in più di quelli possibili in parallelo, ad esempio se avessimo quattro cache e facessimo l’accesso a 5 linee allineate, genereremmo sempre una miss.

Fonte: Memoria e Periferiche.md

2. Pseudo-LRU

Motivazione: L’LRU vero richiede hardware complesso, specialmente per cache con molte vie. Il pseudo-LRU offre un compromesso tra prestazioni e complessità hardware.

Implementazione nei processori x86:

Tuttavia, nel processore x86, è stato implementato uno pseudo-LRU a 3bit

Fonte: Memoria e Periferiche.md

Algoritmo pseudo-LRU per 4 vie:

Dal file Memoria e Periferiche.md:

Stato iniziale: 000 (b0 b1 b2)

Sequenza di accessi (assumendo sempre miss):

  1. Primo accesso: Salvato in cache A seguendo percorso b0-b1
    • Bit invertiti → Nuovo stato: 110
  2. Secondo accesso: Salvato in cache C seguendo percorso b0-b2
    • Nuovo stato: 011
  3. Terzo accesso: Salvato in cache B
    • Nuovo stato: 101
  4. Quarto accesso: Salvato in cache D
    • Stato ritorna a: 000

Struttura ad albero:

L’algoritmo usa un albero binario dove ogni nodo interno rappresenta un bit di decisione che indica quale sottoalbero è stato usato più di recente.

Vantaggi del Pseudo-LRU:

  1. Semplicità hardware: Solo 3 bit per 4 vie (vs 5 bit per LRU vero)
  2. Buone prestazioni: Approssima bene l’LRU nella maggior parte dei casi
  3. Scalabilità: L’overhead cresce logaritmicamente con il numero di vie

Svantaggi del Pseudo-LRU:

Questa politica si chiama pseudo-LRU perché, ipotizzando di aver appena salvato una cacheline in C, il prossimo miss salverà la cacheline in B. Quando, magari, in realtà abbiamo fatto un accesso più vecchio a D che dovrebbe essere lui a cambiare.

Fonte: Memoria e Periferiche.md

Limitazioni:

- ALTRE POLITICHE DI SOSTITUZIONE

3. FIFO (First In, First Out) Vantaggi:

Svantaggi:

4. Random Vantaggi:

Svantaggi:

5. NMRU (Not Most Recently Used) Vantaggi:

Svantaggi:

- CONSIDERAZIONI PRATICHE

Scelta della politica:

La scelta dipende da:

  1. Vincoli hardware: Complessità accettabile del controllore cache
  2. Pattern di accesso: Caratteristiche dell’applicazione
  3. Costi/benefici: Trade-off tra prestazioni e risorse hardware

Impatto sulle prestazioni:

Questo è ciò che genera gli “scalini” nel grafico visto all’inizio e qui riproposto nel dettaglio: Dalla pendenza del singolo scalino si può dedurre quante cache associative abbiamo.

Fonte: Memoria e Periferiche.md

Collegamento con il TLB:

Dal file Paginazione.md:

Inseriamo quindi una cache alla MMU chiamata TLB (Translation Lookaside Buffer).

Il TLB utilizza anch’esso politiche di sostituzione simili per gestire le traduzioni degli indirizzi virtuali.

- RIEPILOGO COMPARATIVO

Politica Complessità HW Prestazioni Vantaggi Svantaggi
LRU Alta Ottime Ottimale teorico Hardware complesso
Pseudo-LRU Media Buone Buon compromesso Non perfettamente ottimale
FIFO Bassa Discrete Semplice Ignora località temporale
Random Minima Variabili Immune a pattern strani Imprevedibile

Conclusioni:

Le politiche di sostituzione rappresentano un compromesso fondamentale nell’architettura delle cache. Il pseudo-LRU emerge come soluzione preferita nei processori moderni perché bilancia efficacemente:

L’evoluzione dalle cache a indirizzamento diretto alle cache associative con politiche sofisticate di sostituzione rappresenta uno dei progressi chiave nell’architettura dei processori moderni, permettendo di sfruttare al meglio i principi di località pur gestendo i conflitti in modo intelligente.

Domanda 2.6 (answered)

Domanda: Come funziona la cache associativa per insiemi? Confronti con quella a indirizzamento diretto.

Risposta: La cache associativa per insiemi è un’evoluzione della cache a indirizzamento diretto che risolve il problema dei conflitti tra cacheline allineate naturalmente.

Cache a indirizzamento diretto - problemi:

Con questo tipo di cache, detta ad indirizzamento diretto, si possono generare conflitti tra sezioni. In particolare, le sezioni che possono fare conflitto in una stessa locazione sono ${\dim{(\mathbf{RAM})} \over \dim{(\mathbf{cache})}}$, ovvero quelle allineate naturalmente a l, con l che indica il numero di cache line disponibili.

Questo tipo di cache è particolarmente poco efficente quando cerchiamo di accedere a due cacheline in memoria allineate naturalmente alla dimensione della cache. In questo caso ogni accesso causa una miss, proprio perché i due indirizzi collidono.

Fonte: Memoria e Periferiche.md

Funzionamento della cache associativa per insiemi:

Si basano sulle cache ad indirizzamento diretto. Infatti non sono altro che più cache allineate tra di loro:

L’esempio a destra è con due cache.

Si utilizzano le due cache in parallelo, in caso di conflitti, andremo a sovrascrivere la cacheline che non si utilizza da più tempo.

Fonte: Memoria e Periferiche.md

Gestione della sostituzione - Registro LRU:

Oltre alle cache, si introduce anche un ulteriore registro R che contiene tanti bit quanti sono necessari per ricordare l’ordinamento delle scritture.

In caso di due vie in R è sufficente 1bit, che codifica quale delle due cache non si utilizza da più tempo in quella line. In caso di quattro vie il registro viene chiamato LRU e contiene 5bit.

Tuttavia, nel processore x86, è stato implementato uno pseudo-LRU a 3bit

Fonte: Memoria e Periferiche.md

Limitazioni della cache associativa per insiemi:

Tuttavia anche con il registro LRU è possibile generare sempre miss. Basta infatti effettuare un accesso in più di quelli possibili in parallelo, ad esempio se avessimo quattro cache e facessimo l’accesso a 5 linee allineate, genereremmo sempre una miss.

Fonte: Memoria e Periferiche.md

Vantaggi principali del confronto:

Domanda 2.7 (answered)

Domanda: Cosa sono le politiche write-through e write-back? Quando si usano?

Risposta: Le politiche write-through e write-back determinano quando e come vengono effettuate le scritture in memoria principale (RAM) quando si verifica un hit di scrittura nella cache. La scelta della politica influenza le prestazioni, la coerenza dei dati e la complessità del sistema.

Contesto delle politiche di scrittura:

Le politiche di scrittura entrano in gioco durante le operazioni di scrittura in cache. Dal file Memoria e Periferiche.md:

Quando il processore richiede una locazione di memoria, si effettua un controllo per verificare che si trovi o meno nella cache. Il segnale di hit indica che la memoria si trova già nella cache, perciò è sufficente leggere quella.

- POLITICHE DI SCRITTURA

1. Write-Through (Scrittura Diretta)

Definizione:

In caso di scrittura con hit abbiamo due possibili politiche:

Fonte: Memoria e Periferiche.md

Meccanismo:

Vantaggi del Write-Through:

1. Semplicità di gestione:

2. Interazione con DMA semplificata:

Dal file DMA.md:

È il caso più semplice poiché all’inizio del trasferimento tutte le cacheline eventualmente presenti contengono lo stesso valore delle corrispondenti cacheline in RAM. Questo implica che non ci sono problemi nel caso di operazione di uscita su DMA (lettura), poiché i dati in RAM sono aggiornati coerentemente con le modifiche salvate nelle cacheline.

Svantaggi del Write-Through:

1. Prestazioni ridotte:

2. Inefficienza per scritture multiple:

2. Write-Back (Scrittura Ritardata)

Definizione:

Fonte: Memoria e Periferiche.md

Meccanismo:

Implementazione del Dirty Bit:

Per migliorare il tempo si aggiunge un’ulteriore bit alle etichette chiamato D (Dirty) che identifica se in una determinata cache-line sono avvenute o meno scritture.

Fonte: Memoria e Periferiche.md

Vantaggi del Write-Back:

1. Prestazioni superiori:

Per quanto riguarda la write-back, la scrittura verrà comunque eseguita in RAM prima o poi, nel peggiore dei casi quando quella cache line viene sostituita. Il guadagno del non fare direttamente il write-through si vede quando effettuiamo un numero molto elevato di scritture nella stessa cache-line.

Fonte: Memoria e Periferiche.md

2. Efficienza del bus:

Svantaggi del Write-Back:

1. Complessità hardware:

2. Problemi di coerenza:

Dal file DMA.md:

In questa politica le scritture della CPU vengono mantenute soltanto in cache e effettuate in maniera sincrona in secondi momenti (come quando la cacheline dirty verrebbe sovrascritta). Le cacheline ~dirty invece continuano a contenere le stesse informazioni della RAM.

Questa politica comporta un problema sia nelle operazioni di uscita su DMA, poiché il buffer di lettura in RAM potrebbe contenere memoria non aggiornata.

- INTERAZIONE CON IL DMA

Write-Through e DMA:

Gestione semplificata:

Soluzioni hardware (Intel):

Nei processori Intel la soluzione è risolta in hardware. Si fa in modo che il controllore cache osservi tutte le possibili sorgenti di scritture in RAM attraverso il bus condiviso, processo chiamato di snooping. Se le linee di controllo identificano un operazione di scrittura, il controllore può usare il contenuto delle linee di indirizzo per eseguire una normale ricerca in cache, e nel caso di hit invalidare in autonomia la corrispondente cacheline.

Fonte: DMA.md

Soluzioni software (ARM):

Nei sistemi ARM il problema è invece delegato al software, tramite istruzioni dedicate che permettono alla CPU di interagire direttamente con il controllore cache e invalidarne le cacheline. Il software dovrà quindi eseguire tutte le istruzioni specificando l’intervallo [b, b+n) (allineato opportunamente alle cacheline) subito dopo che il trasferimento sia terminato.

Fonte: DMA.md

Write-Back e DMA:

Problemi complessi:

Infatti, nelle scritture, il DMA potrebbe andare a modificare solo una parte della cacheline dirty, perciò la mera invalidazione porterebbe a perdere le modifiche effettuate sulle parti di cacheline non comprese nel buffer.

Fonte: DMA.md

Gestione delle letture DMA:

Dal file DMA.md:

Protocollo in più fasi:

  1. Fase di richiesta: Il DMA comunica gli indirizzi al controllore cache
  2. Risposta controllore: Segnala hit/miss e stato del dirty bit
  3. Gestione per casi:
    • miss || (hit && ~dirty): Accesso normale alla RAM
    • hit && dirty: Write-back obbligatorio prima della lettura DMA

Gestione delle scritture DMA:

Dal file DMA.md:

Strategie per hit && dirty:

Soluzione software:

Nella soluzione interamente software, la politica più comune è quella di invalidazione senza write back. Consiste nell’eseguire sempre il write-back di un certo intervallo di indirizzi (quelli del buffer) prima di avviare il trasferimento, invalidandoli successivamente.

Fonte: DMA.md

- POLITICHE PER MISS DI SCRITTURA

Oltre alle politiche per hit, esistono politiche per i miss di scrittura:

Anche in caso di miss la scrittura ha due possibili politiche:

Fonte: Memoria e Periferiche.md

- INTERAZIONE CON LA PAGINAZIONE

Le politiche di scrittura possono essere influenzate dalla paginazione:

Dal file Paginazione.md:

Questo permette di controllare la politica di scrittura a livello di singole pagine di memoria virtuale.

- QUANDO USARE OGNI POLITICA

Write-Through è preferibile quando:

1. Sistemi critici:

2. Sistemi con DMA intensivo:

3. Pattern di scrittura sparsi:

Write-Back è preferibile quando:

1. Sistemi ad alte prestazioni:

2. Sistemi con banda limitata:

3. Cache di grandi dimensioni:

- RIEPILOGO COMPARATIVO

Aspetto Write-Through Write-Back
Prestazioni Più lente Più veloci
Coerenza Sempre garantita Complessa
Hardware Più semplice Più complesso (dirty bit)
Interazione DMA Semplice Complessa
Affidabilità Alta Richiede gestione errori
Traffico bus Alto Basso
Energia Maggiore consumo Minore consumo
Località temporale Non sfruttata Sfruttata efficacemente

- TECNICHE IBRIDE

Alcuni sistemi moderni utilizzano approcci ibridi:

1. Write-through con write buffer:

2. Politiche adaptive:

3. Controllo a livello software:

Conclusioni:

Le politiche write-through e write-back rappresentano un trade-off fondamentale tra prestazioni e semplicità. La scelta dipende dai requisiti specifici del sistema:

La tendenza moderna è verso sistemi write-back con meccanismi sofisticati per gestire la coerenza, specialmente nei processori ad alte prestazioni dove il guadagno in velocità giustifica la complessità aggiuntiva.

Domanda 2.8 (answered)

Domanda: Come interagisce la cache con la memoria virtuale e la paginazione?

Risposta: L’interazione tra cache, memoria virtuale e paginazione rappresenta uno dei meccanismi più complessi e critici per le prestazioni dei sistemi moderni. Questi tre sistemi lavorano a livelli diversi della gerarchia di memoria e devono essere perfettamente coordinati per garantire correttezza ed efficienza.

- Architettura del sistema di memoria:

Ordine di traduzione e caching:

Dal punto di vista architetturale, negli attuali processori Intel/AMD l’ordine di operazione è:

  1. CPU genera indirizzo virtuale
  2. MMU + TLB traducono in indirizzo fisico
  3. Cache utilizza l’indirizzo fisico per il lookup

La memoria cache lavora solo sulla RAM, non ha alcun senso che lavori per l’I/O, poiché manca il principio base (I/O ha effetti collaterali voluti).

Fonte: Memoria e Periferiche.md

TLB: La cache del sistema di paginazione:

Funzione e necessità:

Il TLB (Translation Lookaside Buffer) è essenzialmente una cache specializzata per le traduzioni di indirizzi:

Introducendo la MMU, per ogni accesso in memoria da parte del software, accediamo ad un minimo di 4 tabelle per recuperare l’indirizzo fisico al quale successivamente accedere. Se consideriamo che la MMU deve aggiornare i bit A e D, possiamo arrivare a 8 accessi o persino 12 nei casi peggiori. Ciò riguarda anche gli accessi in cache.

Tutto questo processo non fa altro che rallentare la nostra CPU.

Inseriamo quindi una cache alla MMU chiamata TLB (Translation Lookaside Buffer).

Fonte: Paginazione.md

Meccanismo del TLB:

Lo scopo della TLB è di ricordare le traduzioni utilizzate più recentemente, dove per traduzioni intendiamo ciò che è contenuto nei descrittori di livello 1, insieme alle informazioni accessorie.

Quando MMU accede alla memoria tramite un’indirizzo virtuale, può quindi salvare nel TLB la sua traduzione. Agli accessi successivi si controllerà prima se in TLB è già presente il descrittore che si sta cercando, altrimenti ci si comporta come descritto fin’ora, tramite table-walk.

Fonte: Paginazione.md

Gestione della coerenza nei cambi di contesto:

Invalidazione del TLB:

Questo processo è obbligatorio nei cambi di contesto, in quanto le traduzioni di P1 non hanno senso per P2. Nei processori Intel questo svuotamento avviene in automatico quando viene scritto %cr3, anche se viene cambiato in se stesso. (MOV %cr3, %cr3)

Fonte: Paginazione.md

Problemi specifici con i bit A e D:

Il bit A viene settato durante il table-walk, diventa quindi un problema azzerarlo via software. Infatti, se l’indirizzo è presente nel TLB, non viene rieseguito l’accesso al trie. In questo caso la soluzione è quella di azzerare le righe corrispondenti nel TLB prima di effettuare gli accessi che modificano A.

Fonte: Paginazione.md

Politiche di scrittura e coerenza della cache:

Write-Through vs Write-Back:

La scelta della politica di scrittura della cache influenza l’interazione con la memoria virtuale:

1. Write-Through:

È il caso più semplice poiché all’inizio del trasferimento tutte le cacheline eventualmente presenti contengono lo stesso valore delle corrispondenti cacheline in RAM. Questo implica che non ci sono problemi nel caso di operazione di uscita su DMA (lettura), poiché i dati in RAM sono aggiornati coerentemente con le modifiche salvate nelle cacheline.

Fonte: DMA.md

2. Write-Back (più complessa):

Per quanto riguarda la write-back, la scrittura verrà comunque eseguita in RAM prima o poi, nel peggiore dei casi quando quella cache line viene sostituita. Il guadagno del non fare direttamente il write-through si vede quando effettuiamo un numero molto elevato di scritture nella stessa cache-line.

Fonte: Memoria e Periferiche.md

Interazione con DMA e dispositivi esterni:

Snooping hardware per la coerenza:

Nei processori Intel, la coerenza viene mantenuta tramite meccanismi hardware:

Si fa in modo che il controllore cache osservi tutte le possibili sorgenti di scritture in RAM attraverso il bus condiviso, processo chiamato di snooping. Se le linee di controllo identificano un operazione di scrittura, il controllore può usare il contenuto delle linee di indirizzo per eseguire una normale ricerca in cache, e nel caso di hit invalidare in autonomia la corrispondente cacheline.

Fonte: DMA.md

Problema degli indirizzi fisici vs virtuali:

Tuttavia il software utilizza soltanto indirizzi virtuali [b, b+n).

Sono quindi necessari i seguenti accorgimenti per integrare DMA e MMU:

  1. Al DMA andrà comunicato l’indirizzo fisico f(b) e non quello virtuale b

Fonte: DMA.md

Gestione delle pagine nel DMA:

  1. Pinning delle pagine in memoria:
    • Le pagine coinvolte nel DMA vengono marcate come “non swappabili”
    • Il processo non può essere rimosso dalla RAM durante il trasferimento
    • Richiede gestione dello stato delle pagine nel descrittore di processo
  2. Frammentazione fisica:
    • Buffer contigui in memoria virtuale diventano frammentati fisicamente
    • Necessità di utilizzare scatter-gather DMA per buffer non contigui

Bit di controllo e performance:

Bit PWT e PCD per il controllo della cache:

Nella configurazione della memoria virtuale, specifici bit controllano il comportamento della cache:

Dal file Memoria Virtuale nel Nucleo.md:

// [0xa0000, 0xc0000): memoria video
if (map(root_tab, 0xa0000, 0xc0000, BIT_RW|BIT_PWT, identity_map) != 0xc0000)
    return false;
    
// Mappiamo tutti gli altri indirizzi, fino a 4GiB, settando sia PWT che PCD
if (map(root_tab, beg_pci, end_pci, BIT_RW|BIT_PCD|BIT_PWT, identity_map, 2) != end_pci)
    return false;

Traduzioni identità per il kernel:

Problema delle traduzioni nel kernel:

Quando una tabella, a questo punto in un frame, si riferisce alla tabella successiva in un’altro frame, conserva il suo indirizzo fisico, poiché gli indirizzi virtuali esistono solo per la CPU prima dell’attraversamento della MMU.

Questo genera però dei problemi, in quanto il contenuto in %cr3 è appunto un’indirizzo fisico, e la lettura provoca una traduzione non significativa.

Fonte: Paginazione.md

Soluzione delle traduzioni identità:

Nella parte sistema inizializziamo quindi le traduzioni identità, che mappano un indirizzo virtuale x nell’indirizzo fisico x, affinché gli indirizzi virtuali e fisici combacino numericamente.

Questo permette alle esecuzioni in modalità sistema di poter accedere a tutta la RAM, “bypassando” gli indirizzi virtuali, accedendo praticamente agli indirizzi fisici.

Fonte: Paginazione.md

Ottimizzazioni per pagine di grandi dimensioni:

TLB multipli:

La soluzione moderna a questo problema è quella di avere un TLB per ogni dimensione. La traduzione verrà quindi cercata in parallelo in ciascuno dei TLB, come nel caso di TLB a più vie, e verrà selezionata solamente quella desiderata.

Fonte: Paginazione.md

Vantaggi delle pagine grandi:

Utilizzare pagine di 2MiB o 1GiB invece di 4KiB:

Aspetti pratici e ottimizzazioni:

1. Località degli accessi:

2. Sincronizzazione delle invalidazioni:

3. Gestione delle prestazioni:

Conclusioni:

L’interazione tra cache, memoria virtuale e paginazione è fondamentale per le prestazioni moderne perché:

  1. Il TLB è essenzialmente una cache per le traduzioni di indirizzi, riducendo drasticamente l’overhead della paginazione
  2. La cache lavora su indirizzi fisici post-traduzione, garantendo coerenza tra processi diversi
  3. Meccanismi di snooping hardware mantengono automaticamente la coerenza nei sistemi Intel/AMD
  4. Traduzioni identità nel kernel permettono accesso diretto agli indirizzi fisici quando necessario
  5. Bit di controllo specifici (PWT, PCD) permettono controllo granulare del comportamento della cache per diverse regioni di memoria

Senza questa coordinazione, i sistemi moderni sarebbero inutilizzabili a causa dell’overhead eccessivo degli accessi alla memoria. Il TLB in particolare è assolutamente critico: senza di esso, ogni accesso in memoria richiederebbe 4-12 accessi aggiuntivi per la traduzione, rendendo la memoria virtuale impraticabile.

Approfondimenti:

3. Interruzioni

Domanda 3.1 (answered)

Domanda: Spieghi il problema di Dijkstra relativo alla stampa e come le interruzioni lo risolvono. Perché un approccio con checkFlag() troppo frequente o troppo raro non è ottimale?

Risposta: Il problema di Dijkstra è un classico esempio che dimostra la necessità delle interruzioni per gestire efficacemente la sincronizzazione tra CPU e periferiche.

Il problema originale:

Ipotizziamo di avere una tabella contenente due indici:

Vorremmo che venissero stampati le coppie valore $x$-$f(x)$.

Fonte Interruzioni.md

Architettura della stampante:

La stampa degli elementi è gestita tramite una stampante con due registri:

Approccio ingenuo con polling:

Un approccio al problema potrebbe essere questo:

  1. Calcolo $f(x_1)$
  2. Lo inserisco nella stampante
  3. Attendo che la stampa avvenga spettando checkFlag()
  4. Calcolo $f(x_2)$
  5. …

Questo approccio però perde del tempo durante l’attesa di checkFlag(). In particolare potremmo utilizzare questo tempo per precalcolare le $f(x_i)$ successive.

Problemi del polling con frequenza inadeguata:

Troppo raro:

checkFlag();
for(int i = 0; i < 1000000; ++i)
	a += i;
checkFlag();

Troppo frequente:

for(int i = 0; i < 1000000; ++i){
	checkFlag()
	a += i;
}

Soluzione con interruzioni:

Implementiamo quindi una modifica hardware che ci permetta poi di implementare le routine degli eventi in software.

Meccanismo hardware:

Quello che possiamo fare per supportare gli eventi di questa interfaccia è collegare fisicamente il bit della stampante alla CPU e aggiungere una $\mu$-istruzione che controlla il bit al termine di ogni istruzione.

Vantaggi delle interruzioni:

  1. Efficienza: La CPU può continuare a calcolare le funzioni $f(x)$ senza perdere tempo in polling
  2. Reattività: Risposta immediata quando la stampante è pronta
  3. Ottimizzazione: Utilizzo ottimale delle risorse di sistema

Gestione della singola richiesta:

Il processore vede continuamente il segnale READY come settato ricevendo di fatto infinite richieste, quando in realtà vogliamo solamente una richiesta singola.

Per rimediare a questi problemi è sufficente inserire un generatore di impulsi e un FF-SR che verrà resettato quando la richiesta sarà stata già presa in attenzione.

Controllo del flusso delle interruzioni:

Per quanto riguarda la gestione delle interruzioni durante routine, nel processore intelx86 esiste un flag aggiuntivo in RFLAG, chiamato IF (Interrupt Flag). Se il bit è resettato, il processore non accetta nuove richieste finché non ha terminato quella attuale.

Questo approccio risolve elegantemente il problema di Dijkstra permettendo alla CPU di massimizzare l’utilizzo computazionale mentre mantiene una sincronizzazione perfetta con le periferiche.

Domanda 3.2 (answered)

Domanda: Descriva il meccanismo hardware delle interruzioni APIC. Come viene risolto il problema delle interruzioni a più sorgenti?

Risposta: L’APIC (Advanced Programmable Interrupt Controller) è un controllore delle interruzioni che risolve il problema della gestione di più sorgenti di interrupt in modo elegante ed efficiente.

Architettura hardware dell’APIC:

Il controllore è collegato alle periferiche tramite tre fili, ognuna collegata ad un piedino noto dalle specifiche. Nel nostro calcolatore i dispositivi rilevanti sono connessi ai seguenti piedini

Quando uno di questi segnali viene settato l’APIC invia alla CPU un segnale tramite un suo registro interno chiamato INTR (INTervall Request), inizializzando un handshake.

Fonte: Interruzioni.md

Meccanismo di gestione delle interruzioni multiple:

L’APIC risolve il problema delle interruzioni a più sorgenti attraverso diversi registri specializzati da 256 bit:

Per gestire le richieste di interruzione, l’APIC, oltre a EOI, possiede altri due registri a 256bit:

Fonte: Interruzioni.md

Sistema di priorità e tipizzazione:

Il programmatore assegna un tipo (8 bit) a ogni piedino dell’APIC:

Il programmatore ha quindi il compito di assegnare una precedenza alle varie richieste, e lo fa tramite il tipo.

Quando assegna un tipo il programmatore ha 8bit, dove i 4 più significativi indicano la classe di precedenza.

Se arriva una nuova richiesta che ha classe strettamente maggiore l’APIC invierà una nuova richiesta, negli altri casi attenderà EOI, per poi inviare la successiva richiesta con classe più alta in IRR.

Fonte: Interruzioni.md

Protocollo di handshake:

Per permettere di capire chi è la sorgente del segnale, il programmatore associa ad ogni piedino del controllore APIC un tipo, ovvero una codifica su 8bit.

Nel momento in cui la CPU accetta la richiesta, si prepara inviando il segnale di handshake tramite il filo INTA: INTervall Acknowledge.

Successivamente l’APIC carica il tipo sul bus così che la CPU lo possa leggere.

Fonte: Interruzioni.md

Configurazione software dell’APIC:

Dal file IO.md:

// Associazione irq->tipo (tramite l'APIC)
apic::set_VECT(irq, tipo);
apic::set_MIRQ(irq, false);  // abilita l'interruzione
gate_init(tipo, routine);    // associa routine al tipo

L’APIC risolve così il problema delle interruzioni multiple attraverso: vectorizzazione delle interruzioni per identificare la sorgente, sistema di priorità basato sui tipi, registri ISR/IRR per tracking delle interruzioni, e protocollo EOI per la sincronizzazione.

Domanda 3.3 (answered)

Domanda: Spieghi il ruolo dei registri ISR (In Service Register) e IRR (Interrupt Request Register) nell’APIC. Come funziona il meccanismo di EOI (End Of Interrupt)?

Risposta: I registri ISR e IRR sono componenti fondamentali dell’APIC per la gestione delle interruzioni multiple e la loro sincronizzazione.

Funzione dei registri APIC:

Per gestire le richieste di interruzione, l’APIC, oltre a EOI, possiede altri due registri a 256bit:

Fonte: Interruzioni.md

Dispositivi collegati:

Nel nostro calcolatore i dispositivi rilevanti sono connessi ai seguenti piedini

Meccanismo di handshake:

Quando uno di questi segnali viene settato l’APIC invia alla CPU un segnale tramite un suo registro interno chiamato INTR (INTervall Request), inizializzando un handshake.

Meccanismo EOI (End Of Interrupt):

Per evitare comportamenti indesiderati da parte dell’APIC è importante che questo bit venga settato quando tutta la routine è terminata e non c’è altro da fare. Se così non fosse, il controllore potrebbe reinviare segnali di interruzioni su eventi già gestiti.

Esempio pratico nel codice: Dal file IO.md - Configurazione APIC:

// Associazione irq->tipo (tramite l'APIC)
apic::set_VECT(irq, tipo);
// Smascheriamo le richieste irq nell'APIC
apic::set_MIRQ(irq, false);

E nell’handler:

a_wfi:
	CALL salva_stato
	CALL apic_send_EOI  ; ← Invio EOI all'APIC

Funzionamento dettagliato:

  1. IRR: Tiene traccia delle richieste ricevute ma non ancora elaborate
  2. ISR: Tiene traccia delle interruzioni attualmente in elaborazione
  3. EOI: Segnala la fine dell’elaborazione e permette all’APIC di elaborare nuove richieste

Domanda 3.4 (answered)

Domanda: Descriva il funzionamento delle interruzioni e la scrittura delle routine. Come mai si usa int e non call per le interruzioni?

Risposta: Il funzionamento delle interruzioni e la scrittura delle routine coinvolgono meccanismi hardware e software complessi per garantire una gestione sicura ed efficiente degli eventi asincroni.

Funzionamento hardware delle interruzioni:

Controllo periodico:

Quello che possiamo fare per supportare gli eventi di questa interfaccia è collegare fisicamente il bit della stampante alla CPU e aggiungere una $\mu$-istruzione che controlla il bit al termine di ogni istruzione.

Fonte: Interruzioni.md

Salvataggio dello stato:

Quando il processore accetta un’interruzione salva nella pila diverse informazioni, tra le quali:

Fonte: Interruzioni.md

Gestione delle interruzioni multiple - APIC:

Meccanismo di identificazione:

Per permettere di capire chi è la sorgente del segnale, il programmatore associa ad ogni piedino del controllore APIC un tipo, ovvero una codifica su 8bit.

Nel momento in cui la CPU accetta la richiesta, si prepara inviando il segnale di handshake tramite il filo INTA: INTervall Acknowledge.

Successivamente l’APIC carica il tipo sul bus così che la CPU lo possa leggere.

Fonte: Interruzioni.md

Collegamento dispositivi:

Nel nostro calcolatore i dispositivi rilevanti sono connessi ai seguenti piedini

Fonte: Interruzioni.md

Scrittura delle routine di interruzione:

Struttura base delle routine:

#include <libce.h>
	.global a_tastiera
	.extern c_tastiera
a_tastiera:
	salva_registri
	call c_tastiera
	carica_registri
	iretq

Fonte: Interruzioni.md

Regole fondamentali:

Nelle routine ci sono alcune regole da seguire:

  1. Ricordarsi di settare e resettare correttamente IF tramite le istruzioni STI e CLI
  2. Utilizzare l’istruzione IRETq piuttosto che RET. IRETq infatti si ripristina lo stato del processore a prima che la routine iniziasse, in particolare ripristina RFLAG e gli altri registri prima di ripristinare RIP.

Fonte: Interruzioni.md

Salvataggio dei registri:

Per ovviare anche a questo la soluzione è quella di salvare il contenuto di tutti i registri nella pila. In assembly su 64bit non esistono equivalenti della PUSHAD/POPAD, ma possiamo utilizzare una macro messa a disposizione dalla libreria

Fonte: Interruzioni.md

Perché si usa INT e non CALL:

1. Cambio di contesto e protezione: La differenza fondamentale tra INT e CALL riguarda la protezione del sistema e il cambio di contesto tra livelli di privilegio.

Motivazione della protezione:

Per far funzionare ciò dobbiamo quindi togliere agli utenti la possibilità di poter sfruttare le interruzioni, permettendo loro però di poter comunque chiamare le routine e utilizzarle.

La intel ha adottato un sistema diverso, introducendo un nuovo operando assembler INT $tipo che fa da gate per chiamare la routine (primitiva di sistema) e passare in modalità sistema. $tipo è un numero tra 0 e 255, ed ha lo stesso significato del tipo delle eccezioni e delle interruzioni esterne.

Fonte: Protezione.md

2. Meccanismo di attraversamento del gate: Quando si usa INT, il processore esegue una sequenza complessa:

  1. Innanzitutto il processore si procura il tipo dell’interruzione
  2. Verifica se il bit P associato al tipo è zero, generando un’eccezione di gate non presente 11 in caso positivo
  3. Se sta gestendo una interruzione software o int3, confronta il livello corrente con il campo DPL del gate.
  4. Altrimenti, confronta CS con L. Se L è inferiore, si genera ancora un’eccezione di protezione 13.
  5. Negli altri casi, il processore salva in un registro di appoggio (chiamiamolo SRSP) il contenuto corrente di RSP
  6. Se CS è diverso da L esegue un cambio di pila
  7. Salva in pila 5 long word [SS, SRSP, RFLAGS, CS, RIP]

Fonte: Protezione.md

3. Controllo di accesso: La IDT fornisce un controllo granulare degli accessi:

Ogni gate della IDT occupa 16Byte e contiene le segueni informazioni:

Fonte: Protezione.md

4. Differenze principali tra INT e CALL:

Aspetto CALL INT
Livello di privilegio Rimane invariato Può aumentare (utente → sistema)
Pila Usa la stessa pila Cambia pila se necessario
Protezione Nessun controllo Controlli DPL e protezione
Salvataggio stato Solo RIP RIP, CS, RFLAGS, RSP, SS
Ritorno RET IRETQ
Accesso IDT No Sì, tramite $tipo

5. Necessità del cambio pila:

Il cambio di pila è necessario, è ha due motivazioni:

Fonte: Protezione.md

Configurazione software delle interruzioni:

Esempio di configurazione:

// Associazione irq->tipo (tramite l'APIC)
apic::set_VECT(irq, tipo);
// Associazione tipo->handler (tramite la IDT)
gate_init(tipo, routine);
// Abilitazione interruzioni
apic::set_MIRQ(irq, false);

Fonte: IO.md

Gestione dell’End Of Interrupt:

Per evitare comportamenti indesiderati da parte dell’APIC è importante che questo bit venga settato quando tutta la routine è terminata e non c’è altro da fare. Se così non fosse, il controllore potrebbe reinviare segnali di interruzioni su eventi già gestiti.

Fonte: Interruzioni.md

Conclusioni: L’istruzione INT è fondamentale perché fornisce un meccanismo sicuro e controllato per:

  1. Passare da contesto utente a sistema mantenendo la protezione
  2. Salvare completamente lo stato del processore
  3. Cambiare pila per evitare corruzione dei dati
  4. Controllare l’accesso tramite i gate della IDT
  5. Gestire le interruzioni asincrone in modo trasparente

Una semplice CALL non può garantire questi requisiti di sicurezza e controllo necessari in un sistema operativo moderno.

Domanda 3.5 (answered)

Domanda: Cosa sono le interruzioni esterne? A che serve la apic_send_EOI()?

Risposta: Le interruzioni esterne sono eventi asincroni generati da dispositivi hardware esterni al processore, che richiedono attenzione immediata della CPU per gestire operazioni di I/O o eventi temporizzati.

Definizione e caratteristiche delle interruzioni esterne:

Natura degli eventi:

Il processore lavora su un flusso di controllo, determinato esclusivamente e univocamente da software. Il programmatore però potrebbe utilizzare un modello di programmazione diverso, in grado di associare i programmi a degli eventi. Questi eventi sono un numero finito e ben stabilito, ed il programmatore vi può associare una propria routine.

Fonte: Interruzioni.md

Timing delle interruzioni esterne:

Quello che possiamo fare per supportare gli eventi di questa interfaccia è collegare fisicamente il bit della stampante alla CPU e aggiungere una $\mu$-istruzione che controlla il bit al termine di ogni istruzione.

Fonte: Interruzioni.md

Differenza con le interruzioni interne: A differenza delle eccezioni (interruzioni interne), le interruzioni esterne:

Dispositivi che generano interruzioni esterne:

Nel nostro sistema i principali dispositivi sono:

Nel nostro calcolatore i dispositivi rilevanti sono connessi ai seguenti piedini

Fonte: Interruzioni.md

Gestione tramite APIC:

Meccanismo di controllo:

Per gestire tutte le richieste viene introdotto una nuova componente, detto Controllore delle Interruzioni l’APIC (Advanced Programmable Interrupt Controller).

Fonte: Interruzioni.md

Registri di gestione:

Per gestire le richieste di interruzione, l’APIC, oltre a EOI, possiede altri due registri a 256bit:

Fonte: Interruzioni.md

La funzione apic_send_EOI():

Scopo principale: La funzione apic_send_EOI() (End Of Interrupt) serve a comunicare all’APIC che la gestione dell’interruzione è stata completata, permettendo al controllore di accettare nuove richieste.

Meccanismo di controllo su livello:

Per capire se c’è una nuova richiesta o meno, si utilizza un metodo software chiamato controllo su Livello. Questo tipo di controllo fa in modo che l’APIC, dopo aver inviato una richiesta, guardi nuovamente i piedini solo dopo aver ricevuto il segnale di gestione completata dell'interruzione.

Fonte: Interruzioni.md

Importanza del timing:

Per evitare comportamenti indesiderati da parte dell’APIC è importante che questo bit venga settato quando tutta la routine è terminata e non c’è altro da fare. Se così non fosse, il controllore potrebbe reinviare segnali di interruzioni su eventi già gestiti.

Fonte: Interruzioni.md

Esempio pratico nel codice:

Struttura tipica di un handler: Dal file IO.md:

; `sistema.s`

a_wfi:
	CALL salva_stato
	CALL apic_send_EOI  ; ← Invio EOI all'APIC
	CALL schedulatore
	CALL carica_stato
	RET

In una routine C++:

extern "C" void c_tastiera(){
    /* Implementazione della gestione */
    
    // Processamento del carattere dalla tastiera
    array_des_io[0].buf[quanti_letti] = char(inputb(array_des_io[0].iOUT));
    quanti_letti++;
    
    if(quanti_letti == array_des_io[0].quanti) {
        // Operazione completata - risveglia processo
        quanti_letti = 0;
        sem_signal(array_des_io[0].sync);
    }
    
    apic::setEOI();         // IMPORTANTE: Segnala fine gestione
}

Funzionamento del protocollo EOI:

  1. IRR: Tiene traccia delle richieste ricevute ma non ancora elaborate
  2. ISR: Tiene traccia delle interruzioni attualmente in elaborazione
  3. EOI: Segnala la fine dell’elaborazione e permette all’APIC di:
    • Rimuovere l’interruzione da ISR
    • Elaborare nuove richieste in IRR
    • Ristabilire la priorità normale del sistema

Conseguenze della mancanza di EOI: Senza apic_send_EOI():

RIEPILOGO: Le interruzioni esterne sono il meccanismo fondamentale che permette ai dispositivi hardware di comunicare asincronamente con la CPU, mentre apic_send_EOI() è essenziale per mantenere il corretto flusso di controllo e sincronizzazione nel sistema di gestione delle interruzioni.

Domanda 3.6 (answered)

Domanda: Descriva l’annidamento delle interruzioni con l’utilizzo dei due registri ISR e IRR. Cosa comporta programmare con le interruzioni attive?

Risposta: L’annidamento delle interruzioni è un meccanismo che permette di gestire richieste di interruzione multiple con diversi livelli di priorità, utilizzando i registri ISR e IRR dell’APIC per tracciare e coordinare l’esecuzione.

Meccanismo di annidamento con ISR e IRR:

Registri fondamentali dell’APIC:

Per gestire le richieste di interruzione, l’APIC, oltre a EOI, possiede altri due registri a 256bit:

Fonte: Interruzioni.md

Gestione delle priorità:

Il programmatore ha quindi il compito di assegnare una precedenza alle varie richieste, e lo fa tramite il tipo. Quando assegna un tipo il programmatore ha 8bit, dove i 4 più significativi indicano la classe di precedenza.

Fonte: Interruzioni.md

Logica di annidamento:

Se arriva una nuova richiesta che ha classe strettamente maggiore l’APIC invierà una nuova richiesta, negli altri casi attenderà EOI, per poi inviare la successiva richiesta con classe più alta in IRR.

Fonte: Interruzioni.md

Processo di annidamento dettagliato:

1. Arrivo delle richieste:

2. Accettazione da parte della CPU:

In ogni caso l'ultima parola sull'eseguire in maniera effettiva o meno l'interruzione spetta alla CPU. Solamente quando la CPU invierà il segnale di INTA l’APIC sceglierà la richiesta di classe più elevata in IRR e la sposterà in ISR.

Fonte: Interruzioni.md

3. Gestione delle interruzioni concorrenti:

Se manteniamo il IF = 1, quando avvengono due richieste di interruzione dobbiamo porci la domanda se abbia senso interrompere la prima interruzione o attendere prima che questa venga completata.

Fonte: Interruzioni.md

Controllo del flag IF:

Il comando gate_init() ha un terzo parametro settato di default su false, che imposta IF = 0 durante le routine, affinché non possano essere interrotte. Se volessimo invece che una routine possa essere interrotta, dobbiamo impostarlo esplicitamente a true.

Fonte: Interruzioni.md

Cosa comporta programmare con le interruzioni attive:

1. Problemi di concorrenza - “Vaso di Pandora”:

Il problema di quando più flussi operano sulle stesse variabili è stato chiamato “Vaso di Pandora” da Dijsktra. La gestione di questi casi può diventare infatti estremamente complessa.

Fonte: Interruzioni.md

2. Interferenze tra flussi di esecuzione: Dal file Realizzazione Primitive.md:

Più in generale, quello che abbiamo descritto è un problema di interferenza tra due flussi di esecuzione che lavorano su una stessa struttura dati. La causa di queste interferenze è dovuta alle interruzioni, poiché rende visibili ad altri processi gli stati inconsistenti dovute a espressioni non atomiche.

3. Gestione dei registri:

Un altro errore comune generato dalle interruzioni è quello di sovrascrivere i registri utilizzati dal flusso principale. Questo succede per via di una convenzione, che stabilisce che alcuni registri sono ad utilizzo libero, e non è quindi richiesto alle funzioni di ripristinarli al termine della loro esecuzione.

Fonte: Interruzioni.md

Soluzioni per programmare con interruzioni attive:

1. Salvataggio completo dei registri:

#include <libce.h>
	.global a_tastiera
	.extern c_tastiera
a_tastiera:
	salva_registri
	call c_tastiera
	carica_registri
	iretq

Fonte: Interruzioni.md

2. Controllo selettivo delle interruzioni:

Interrompere le interruzioni è ovviamente un’operazione lecita, dopotutto le interruzioni funzionano a pila, e non vanno a toccarsi tra di loro se ben gestite.

Fonte: Interruzioni.md

3. Gestione delle priorità strategica:

La scelta ricade esclusivamente sulla priorità che il programmatore dà alle varie interruzioni, e può cambiare da caso a caso: attendere per la visualizzazione di un carattere a schermo può non provocare problemi, mentre se abbiamo una richiesta attraverso il timer, non gestirla può provocare perdita di richieste, e quindi ha più senso interrompere anche le eventuali interruzioni.

Fonte: Interruzioni.md

Esempio pratico di annidamento:

Scenario: Timer (priorità alta) interrompe routine tastiera (priorità bassa)

  1. Tastiera attiva: Richiesta memorizzata in IRR, spostata in ISR quando accettata
  2. Timer arriva: Richiesta con priorità maggiore in IRR
  3. APIC invia nuova richiesta: Timer può interrompere la routine tastiera
  4. Esecuzione annidata:
    • Timer esegue con IF=0 (non interrompibile)
    • Al termine: apic_send_EOI() per timer
    • Ripresa routine tastiera dal punto di interruzione

Vantaggi e sfide:

Vantaggi:

Sfide:

RIEPILOGO: L’annidamento delle interruzioni con ISR/IRR fornisce un sistema robusto per gestire eventi multipli con priorità, ma richiede attenzione particolare nella programmazione per evitare interferenze e garantire la correttezza del sistema.

Domanda 3.7 (answered)

Domanda: Quando si accodano le richieste di interruzione su IRR? Perché quando si attraversa il gate viene salvato il registro dei flag?

Risposta: Le richieste di interruzione si accodano nell’IRR in momenti specifici determinati dalla gestione delle priorità dell’APIC, mentre il salvataggio del registro dei flag durante l’attraversamento del gate è essenziale per preservare lo stato del processore e garantire un ritorno corretto al contesto precedente.

Accodamento delle richieste in IRR:

Meccanismo dell’IRR (Interrupt Request Register):

Per gestire le richieste di interruzione, l’APIC, oltre a EOI, possiede altri due registri a 256bit:

Fonte: Interruzioni.md

Quando avviene l’accodamento:

1. Ricezione della richiesta: Quando una periferica (tastiera, timer, hard disk) genera un segnale di interruzione sul proprio piedino dell’APIC, la richiesta viene immediatamente memorizzata nell’IRR:

Quando uno di questi segnali viene settato l’APIC invia alla CPU un segnale tramite un suo registro interno chiamato INTR (INTervall Request), inizializzando un handshake.

Per permettere di capire chi è la sorgente del segnale, il programmatore associa ad ogni piedino del controllore APIC un tipo, ovvero una codifica su 8bit.

Fonte: Interruzioni.md

2. Gestione delle priorità:

Il programmatore ha quindi il compito di assegnare una precedenza alle varie richieste, e lo fa tramite il tipo. Quando assegna un tipo il programmatore ha 8bit, dove i 4 più significativi indicano la classe di precedenza.

Se arriva una nuova richiesta che ha classe strettamente maggiore l’APIC invierà una nuova richiesta, negli altri casi attenderà EOI, per poi inviare la successiva richiesta con classe più alta in IRR.

Fonte: Interruzioni.md

3. Controllo della CPU:

In ogni caso l'ultima parola sull'eseguire in maniera effettiva o meno l'interruzione spetta alla CPU. Solamente quando la CPU invierà il segnale di INTA l’APIC sceglierà la richiesta di classe più elevata in IRR e la sposterà in ISR.

Fonte: Interruzioni.md

Timing del controllo delle interruzioni:

Le interruzioni vengono controllate e accettate solo tra un’istruzione e la successiva. Il processore verifica la presenza di richieste di interruzione alla fine di ogni istruzione completata, quando il processore si trova in uno stato consistente.

Fonte: basato su Interruzioni.md

Salvataggio del registro dei flag (RFLAGS):

Necessità del salvataggio: Il salvataggio del registro RFLAGS durante l’attraversamento del gate è cruciale per diversi motivi:

1. Preservazione dello stato del processore:

Quando il processore accetta un’interruzione salva nella pila diverse informazioni, tra le quali:

Fonte: Interruzioni.md

2. Informazioni salvate automaticamente:

  1. Salva in pila 5 long word. In ordine:
    • [0] SS: 1 long word non significativa
    • [1] SRSP: pila salvata al passo 5
    • [2] RFLAGS: registro dei flag
    • [3] CS: vecchio valore del CS da ripristinare successivamente
    • [4] RIP: indirizzo della prima istruzione da eseguire all’uscita del gate

Fonte: Protezione.md

3. Gestione del flag IF (Interrupt Flag):

Per quanto riguarda la gestione delle interruzioni durante routine, nel processore intelx86 esiste un flag aggiuntivo in RFLAG, chiamato IF (Interrupt Flag). Se il bit è resettato, il processore non accetta nuove richieste finché non ha terminato quella attuale.

Fonte: Interruzioni.md

Controllo dei gate:

Il comando gate_init() ha un terzo parametro settato di default su false, che imposta IF = 0 durante le routine, affinché non possano essere interrotte. Se volessimo invece che una routine possa essere interrotta, dobbiamo impostarlo esplicitamente a true.

Fonte: Interruzioni.md

4. Ripristino trasparente: Il salvataggio di RFLAGS permette al processore di tornare esattamente allo stato precedente quando la routine termina:

Utilizzare l’istruzione IRETq piuttosto che RET. IRETq infatti si ripristina lo stato del processore a prima che la routine iniziasse, in particolare ripristina RFLAG e gli altri registri prima di ripristinare RIP.

Fonte: Interruzioni.md

Interazione IRR-ISR durante l’esecuzione:

Flusso completo:

  1. Periferica genera richiesta → Accodamento in IRR
  2. APIC invia INTR → CPU controlla tra istruzioni
  3. CPU accetta con INTA → Movimento da IRR a ISR
  4. Salvataggio automatico → Include RFLAGS nella pila
  5. Esecuzione routine → IF controllato dal tipo di gate
  6. EOI inviato → Bit in ISR azzerato, nuove richieste possibili

RIEPILOGO: Le richieste si accodano in IRR quando le periferiche generano segnali ma la CPU non può ancora accettarle (per priorità o timing), mentre il salvataggio di RFLAGS garantisce che lo stato completo del processore venga preservato durante le transizioni di contesto, permettendo un ritorno trasparente al codice interrotto.

Domanda 3.8 (answered)

Domanda: Come gestiamo le periferiche che agiscono sullo stesso piedino dell’APIC? Quanti piedini ha l’APIC?

Risposta: L’APIC dispone di 24 piedini per la gestione delle interruzioni, e quando più periferiche condividono lo stesso piedino si utilizzano tecniche software per identificare la sorgente effettiva dell’interruzione, spesso attraverso il polling dei registri di stato delle periferiche coinvolte.

Numero di piedini dell’APIC:

Capacità hardware:

In particolare I/O ha una tabella a_p con un entrata per ogni piedino dell’APIC (24 piedini → 24 entrate).

Fonte: IO.md

Questo significa che l’APIC può gestire fino a 24 richieste di interruzione simultanee da altrettante periferiche o gruppi di periferiche.

Dispositivi collegati nel nostro sistema:

Assegnazione dei piedini:

Nel nostro calcolatore i dispositivi rilevanti sono connessi ai seguenti piedini

Fonte: Interruzioni.md

Gestione delle periferiche sullo stesso piedino:

Problema della condivisione: Quando più periferiche condividono lo stesso piedino dell’APIC, sorge il problema di identificare quale periferica specifica ha generato l’interruzione, poiché l’APIC può solo identificare il piedino attivato, non la periferica individuale.

Soluzione attraverso il polling:

1. Meccanismo software di identificazione: Quando un’interruzione arriva su un piedino condiviso, il sistema deve:

  1. Leggere i registri di stato di tutte le periferiche collegate a quel piedino
  2. Identificare quale periferica ha effettivamente richiesto l’interruzione
  3. Gestire la richiesta della periferica corretta
  4. Ripetere il controllo per eventuali altre periferiche pendenti

2. Esempio nel bus PCI: Il problema della condivisione è molto comune nel bus PCI, dove più funzioni possono condividere gli stessi piedini di interruzione:

Ogni dispositivo ha fino a quattro piedini in uscita per le richieste di interruzione: INTA#, INTB#, INTC# e INTD#.

Ogni funzione può quindi essere collegata ad al più uno di questi piedini. Inoltre, funzioni dello stesso dispositivo possono essere collegate allo stesso piedino.

Fonte: PCI.md

3. Identificazione tramite registri di configurazione:

Il piedino utilizzato deve essere leggibile dal registro di configurazione chiamato Intr. Pin, grande 1Byte e di sola lettura. Se vale 0 indica che la funzione non genera interruzione, 1 che utilizza INTA#, 2 che utilizza INTB# e così via…

Nel nostro caso il BIOS scrive in Intr. line proprio il numero del piedino dell’APIC, quindi possiamo limitarci a leggere questo registro.

Fonte: PCI.md

Processo di gestione pratico:

Routine di interruzione condivisa:

extern "C" void c_shared_irq_handler() {
    bool handled = false;
    
    // Controlla ogni periferica collegata al piedino
    for (int dev = 0; dev < NUM_DEVICES_ON_PIN; dev++) {
        if (device_has_pending_interrupt(dev)) {
            handle_device_interrupt(dev);
            handled = true;
        }
    }
    
    // Se nessuna periferica ha richiesto l'interruzione
    if (!handled) {
        // Interruzione spuria o errore
        log_spurious_interrupt();
    }
    
    apic_send_EOI();  // Sempre necessario
}

Vantaggi e svantaggi:

Vantaggi:

Svantaggi:

Tecniche avanzate:

Message Signaled Interrupts (MSI):

Un ultima soluzione moderna prevede invece che le richieste di interruzione non viaggino su linee separate, ma siano inoltrate come speciali transazioni sul bus PCI stesso, sotto forma di scritture a particolari indirizzi chiamati Message Signaled Interrupts.

Fonte: DMA.md

Questa tecnica moderna risolve il problema della condivisione assegnando a ogni periferica un indirizzo univoco per le sue interruzioni, eliminando la necessità di condividere piedini fisici.

RIEPILOGO: L’APIC ha 24 piedini disponibili per le interruzioni. Quando più periferiche condividono lo stesso piedino, il sistema utilizza tecniche software di polling per identificare la sorgente effettiva dell’interruzione, controllando i registri di stato di tutte le periferiche collegate a quel piedino. Le soluzioni moderne come MSI eliminano questo problema assegnando indirizzi univoci a ogni periferica.

Domanda 3.9 (answered)

Domanda: Chi configura i registri dell’APIC e la IDT? Chi stabilisce le classi di priorità nelle interruzioni e come si riconoscono?

Risposta: La configurazione dei registri dell’APIC e della IDT è una responsabilità condivisa tra il BIOS/bootstrap, il kernel/nucleo e il programmatore di sistema, con un meccanismo ben definito per stabilire e riconoscere le classi di priorità delle interruzioni.

Configurazione dei registri dell’APIC:

1. Inizializzazione hardware dal BIOS: Il BIOS configura le informazioni hardware di base per collegare le periferiche ai piedini dell’APIC:

Nel nostro caso il BIOS scrive in Intr. line proprio il numero del piedino dell’APIC, quindi possiamo limitarci a leggere questo registro.

Fonte: PCI.md

2. Configurazione software dal programmatore: Il programmatore di sistema configura i registri dell’APIC tramite apposite funzioni:

Il programmatore associa ad ogni piedino del controllore APIC un tipo, ovvero una codifica su 8bit.

Fonte: Interruzioni.md

Esempio di configurazione APIC:

// Associazione irq->tipo (tramite l'APIC)
apic::set_VECT(irq, tipo);

// Configurazione trigger mode e mask
apic::set_TRGM(2, false);  // fronte/livello
apic::set_MIRQ(irq, false); // abilita interruzione

3. Registri chiave dell’APIC: L’APIC mantiene tre informazioni fondamentali per ogni piedino:

Vedremo successivamente che l’APIC conserva tre informazioni per ogni piedino:

Fonte: Interruzioni.md

Configurazione della IDT (Interrupt Descriptor Table):

1. Inizializzazione dal programma di bootstrap: La IDT viene creata e inizializzata durante il bootstrap del sistema:

La IDT viene inizializzata tramite il programma di bootstrap, in particolare utilizzando l’istruzione LIDTR che carica l’indirizzo della IDT nel registro IDTR che il processore utilizza per accedere ala tabella e allocando IDT nella memoria M1. Per non permettere la modifica di IDT da parte dell’utente l’istruzione LIDTR è anch’essa vietata nel contesto utente.

Fonte: Protezione.md

2. Popolamento delle entry dal kernel: Il kernel popola le singole entry della IDT associando tipi a routine specifiche:

La IDT deve essere allocata dal programmatore, e ogni sua riga viene identificata dal tipo che il programmatore ha precedentemente dato ai piedini dell’APIC.

Fonte: Interruzioni.md

Esempio di configurazione IDT:

// Associazione tipo->handler (tramite la IDT)
gate_init(tipo, routine);

// Esempio specifico
const natb TIM_VECT = 0x50;
apic::set_VECT(2, TIM_VECT);    // piedino 2 → tipo 0x50
gate_init(TIM_VECT, a_timer);   // tipo 0x50 → routine a_timer

3. Processo di collegamento completo nel modulo I/O: Il modulo I/O gestisce la catena completa di configurazione:

Creiamo il collegamento irq->tipo->handler->processo esterno

// irq->tipo (tramite l’APIC) apic::set_VECT(irq, tipo);

// Associazione tipo->handler (tramite la IDT) load_handler(tipo, irq);

// Associazione handler->processo esterno (tramite ‘a_p’) a_p[irq] = p;

Fonte: IO.md

Stabilimento delle classi di priorità:

1. Chi stabilisce le priorità: Le classi di priorità sono stabilite dal programmatore di sistema attraverso la scelta del tipo:

Il programmatore ha quindi il compito di assegnare una precedenza alle varie richieste, e lo fa tramite il tipo. Quando assegna un tipo il programmatore ha 8bit, dove i 4 più significativi indicano la classe di precedenza.

Fonte: Interruzioni.md

2. Schema delle priorità nel modulo I/O: Nel modulo I/O, le priorità seguono uno schema specifico:

La soluzione che adottiamo prevede quindi che tale precedenza debba avere la forma: MIN_EXT_PRIO + prio dove:

Fonte: IO.md

Come si riconoscono le classi di priorità:

1. Struttura del tipo a 8 bit: I 4 bit più significativi del tipo definiscono la classe di priorità:

Tipo (8 bit): [CCCC][PPPP]
              ↑    ↑
              |    └─ Priorità all'interno della classe (4 bit)
              └────── Classe di precedenza (4 bit)

2. Meccanismo di valutazione dell’APIC: L’APIC valuta le priorità automaticamente:

Se arriva una nuova richiesta che ha classe strettamente maggiore l’APIC invierà una nuova richiesta, negli altri casi attenderà EOI, per poi inviare la successiva richiesta con classe più alta in IRR.

Nel caso in cui ci fossero più richieste con la stessa classe di priorità, andrà a discriminare sui 4bit meno significativi, inviando quella con il valore più alto.

Fonte: Interruzioni.md

3. Controllo finale dalla CPU: La CPU ha l’ultima parola sull’accettazione delle interruzioni:

In ogni caso l’ultima parola sull’eseguire in maniera effettiva o meno l’interruzione spetta alla CPU. Solamente quando la CPU invierà il segnale di INTA l’APIC sceglierà la richiesta di classe più elevata in IRR e la sposterà in ISR.

Fonte: Interruzioni.md

Registri per il tracking delle priorità:

Registri ISR e IRR: L’APIC utilizza registri specializzati per tracciare le priorità:

Per gestire le richieste di interruzione, l’APIC, oltre a EOI, possiede altri due registri a 256bit:

Fonte: Interruzioni.md

Esempio pratico di configurazione completa:

Per la tastiera:

const natb KBD_VECT = 0x40;             // Classe 4, priorità 0

apic::set_VECT(1, KBD_VECT);        // Piedino 1 → tipo 0x40
gate_init(KBD_VECT, a_tastiera);    // Tipo 0x40 → routine tastiera
apic::set_MIRQ(1, false);           // Abilita interruzioni
kbd::enable_intr();                 // Abilita hardware tastiera

Per il timer:

const natb TIM_VECT = 0x50;         // Classe 5, priorità 0 (maggiore di tastiera)

apic::set_VECT(2, TIM_VECT);
gate_init(TIM_VECT, a_timer);
apic::set_MIRQ(2, false);

Protezione e sicurezza:

Controlli di accesso: Il sistema garantisce che solo il kernel possa modificare queste configurazioni:

Per non permettere la modifica di IDT da parte dell’utente l’istruzione LIDTR è anch’essa vietata nel contesto utente.

Fonte: Protezione.md

RIEPILOGO:

Domanda 3.10 (answered)

Domanda: Qual è la differenza tra interrupt su fronte e su livello? È possibile che si perdano interruzioni?

Risposta: La differenza tra interrupt su fronte e su livello risiede nel momento e nella modalità con cui l’APIC riconosce e gestisce le richieste di interruzione. Sì, è possibile che si perdano interruzioni in determinate circostanze, particolarmente con la gestione su fronte.

Interrupt su fronte (Edge-triggered):

Modalità di riconoscimento:

È inoltre possibile configurare l’APIC affinché legga le richieste sui fronti di salita o sui fronti di discesa.

Fonte: Interruzioni.md

Caratteristiche degli interrupt su fronte:

1. Riconoscimento su transizione: L’APIC riconosce la richiesta di interruzione nel momento della transizione del segnale (fronte di salita o discesa), non sulla durata del segnale stesso.

2. Configurazione software: Dal codice degli esempi del timer:

apic::set_TRGM(2, false);  // false = riconoscimento su fronte
/*
* Trigger Mode: genera segnale sul piedino 2 quando avviene
*   false=riconoscimento su fronte,
*   true=riconoscimento su livello
*/

3. Vantaggi:

4. Esempio pratico del timer:

extern "C" void c_timer() {
    counter++;
    apic::send_EOI();
}

IL timer genera un’onda quadra. Abbiamo inserito un periodo di 50ms perciò il segnale sarà ad 1 per 25ms e a 0 per 25ms. Se avessimo impostato apic::setTRGM(2, true), avremmo avuto molte più richieste.

Fonte: Interruzioni.md

Interrupt su livello (Level-triggered):

Modalità di riconoscimento: Il controllo su livello è il meccanismo utilizzato dalla maggior parte delle periferiche moderne, inclusa la tastiera.

1. Riconoscimento continuo:

Per capire se c’è una nuova richiesta o meno, si utilizza un metodo software chiamato controllo su Livello. Questo tipo di controllo fa in modo che l’APIC, dopo aver inviato una richiesta, guardi nuovamente i piedini solo dopo aver ricevuto il segnale di gestione completata dell'interruzione.

Fonte: Interruzioni.md

2. Configurazione software:

apic::set_TRGM(1, true);   // true = riconoscimento su livello (default)

3. Meccanismo EOI essenziale:

Per evitare comportamenti indesiderati da parte dell’APIC è importante che questo bit venga settato quando tutta la routine è terminata e non c’è altro da fare. Se così non fosse, il controllore potrebbe reinviare segnali di interruzioni su eventi già gestiti.

Fonte: Interruzioni.md

4. Comportamento con durata prolungata:

Infatti, il segnale è settato per 25ms, che è un tempo molto maggiore del tempo necessario a eseguire la routine, e ogni volta che terminerà la routine la farà ripartire con lo stesso segnale.

Fonte: Interruzioni.md

Possibilità di perdita di interruzioni:

1. Perdita su fronte (Edge-triggered):

Scenario critico: Con la gestione su fronte, se due eventi si verificano in rapida successione, il secondo evento può essere perso se il primo non è ancora stato completamente gestito.

Meccanismo di perdita:

2. Gestione con livello - protezione dalla perdita:

Accodamento in IRR:

Per gestire le richieste di interruzione, l’APIC, oltre a EOI, possiede altri due registri a 256bit:

Fonte: Interruzioni.md

Meccanismo di protezione: Le richieste su livello sono più robuste perché:

3. Controllo finale della CPU:

In ogni caso l’ultima parola sull’eseguire in maniera effettiva o meno l’interruzione spetta alla CPU. Solamente quando la CPU invierà il segnale di INTA l’APIC sceglierà la richiesta di classe più elevata in IRR e la sposterà in ISR.

Fonte: Interruzioni.md

Prevenzione della perdita di interruzioni:

1. Tempistiche adeguate: Per eventi critici che non possono essere persi, la gestione su livello è preferibile.

2. Gestione delle priorità:

La scelta ricade esclusivamente sulla priorità che il programmatore dà alle varie interruzioni, e può cambiare da caso a caso: attendere per la visualizzazione di un carattere a schermo può non provocare problemi, mentre se abbiamo una richiesta attraverso il timer, non gestirla può provocare perdita di richieste, e quindi ha più senso interrompere anche le eventuali interruzioni.

Fonte: Interruzioni.md

3. Tecnologie moderne - Message Signaled Interrupts:

Un ultima soluzione moderna prevede invece che le richieste di interruzione non viaggino su linee separate, ma siano inoltrate come speciali transazioni sul bus PCI stesso, sotto forma di scritture a particolari indirizzi chiamati Message Signaled Interrupts. Poiché prima che la richiesta di interruzione arrivi, il buffer del ponte dovrà essere svuotato dai precedenti contenuti, si risolve anche in questo modo il problema delle corse.

Fonte: DMA.md

RIEPILOGO:

Domanda 3.11 (answered)

Domanda: Quando si traduce una funzione in C++ sono ripristinati tutti i registri? Quali sono le istruzioni che ci permettono di usare le interruzioni?

Risposta: No, quando si traduce una funzione in C++ non sono ripristinati tutti i registri. Il comportamento dipende dalle calling conventions del linguaggio. Le istruzioni fondamentali per le interruzioni sono STI, CLI e IRETQ.

Calling Conventions e gestione dei registri in C++:

1. Convenzioni standard: Le funzioni C++ seguono convenzioni che dividono i registri in categorie:

Un altro errore comune generato dalle interruzioni è quello di sovrascrivere i registri utilizzati dal flusso principale. Questo succede per via di una convenzione, che stabilisce che alcuni registri sono ad utilizzo libero, e non è quindi richiesto alle funzioni di ripristinarli al termine della loro esecuzione. Tra questi registri abbiamo ad esempio il registro %rcx.

Fonte: Interruzioni.md

2. Categorie di registri:

3. Problemi con le interruzioni:

Nel caso in cui sia il nostro flusso principale che la routine utilizzino %rcx la probabilità che il programma abbia dei comportamenti inaspettati è molto elevata.

Fonte: Interruzioni.md

Compilatore e gestione dei registri:

1. Limitazioni del compilatore:

Il compilatore non ha idea di come distinguere le funzioni routine dalle altre. Perciò il comportamento di default segue le classiche politiche di compilazione:

Fonte: Interruzioni.md

2. Salvataggio completo necessario:

Per ovviare anche a questo la soluzione è quella di salvare il contenuto di tutti i registri nella pila. In assembly su 64bit non esistono equivalenti della PUSHAD/POPAD, ma possiamo utilizzare una macro messa a disposizione dalla libreria

Fonte: Interruzioni.md

Istruzioni fondamentali per le interruzioni:

1. STI e CLI - Controllo del flag IF:

Per quanto riguarda la gestione delle interruzioni durante routine, nel processore intelx86 esiste un flag aggiuntivo in RFLAG, chiamato IF (Interrupt Flag). Se il bit è resettato, il processore non accetta nuove richieste finché non ha terminato quella attuale. Per poterlo manipolare esistono due istruzioni:

Fonte: Interruzioni.md

2. IRETQ - Ritorno dalle interruzioni:

Nelle routine ci sono alcune regole da seguire:

  1. Ricordarsi di settare e resettare correttamente IF tramite le istruzioni STI e CLI
  2. Utilizzare l’istruzione IRETq piuttosto che RET. IRETq infatti si ripristina lo stato del processore a prima che la routine iniziasse, in particolare ripristina RFLAG e gli altri registri prima di ripristinare RIP.

Fonte: Interruzioni.md

3. Salvataggio automatico dell’hardware:

Quando il processore accetta un’interruzione salva nella pila diverse informazioni, tra le quali:

Fonte: Interruzioni.md

Struttura completa di una routine di interruzione:

1. Routine assembly corretta:

#include <libce.h>
	.global a_tastiera
	.extern c_tastiera
a_tastiera:
	salva_registri
	call c_tastiera
	carica_registri
	iretq

2. Funzioni di sistema: Dal file Sistemi Multiprocesso e Processi.md:

routine_gate:
    CALL salva_stato        ; Macro che salva il contenuto di tutti i registri in pila
    /*
    * corpo routine
    */
    CALL carica_stato       ; Macro che carica il contenuto di tutti i registri dalla pila
    IRETQ

3. Primitive di sistema:

Le routine avranno quindi tutte lo stesso formato.

a_primitiva_i:
    CALL salva_stato
    CALL c_primitiva;
    CALL carica_stato
    IRETQ

Fonte: Realizzazione Primitive.md

Macro della libreria:

1. salva_registri e carica_registri: Utilizzate per il salvataggio completo in routine di interruzione esterne.

2. salva_stato e carica_stato: Utilizzate per la gestione del contesto dei processi nelle primitive di sistema:

Per capire a quale processo ci stiamo riferendo quando invochiamo salva_stato e carica_stato utilizziamo come già detto una variabile globale esecuzione.

Fonte: Sistemi Multiprocesso e Processi.md

Istruzioni specifiche per controllo interruzioni:

1. Controllo manuale:

2. Gate della IDT:

Il comando gate_init() ha un terzo parametro settato di default su false, che imposta IF = 0 durante le routine, affinché non possano essere interrotte. Se volessimo invece che una routine possa essere interrotta, dobbiamo impostarlo esplicitamente a true.

Fonte: Interruzioni.md

3. Ritorno sicuro: IRETQ è l’unica istruzione che permette il ritorno corretto dalle interruzioni, ripristinando:

RIEPILOGO:

Domanda 3.12 (answered)

Domanda: Come si gestisce il problema del Cavallo di Troia nel contesto delle interruzioni e del sistema di protezione?

Risposta: Il problema del Cavallo di Troia nelle interruzioni e nel sistema di protezione si riferisce a situazioni in cui un processo utente malevolo fornisce deliberatamente indirizzi non validi o pericolosi al sistema, sfruttando la differenza di privilegio tra contesti per accedere o modificare aree di memoria che non dovrebbe.

Definizione del problema:

Questo problema, che ricade nei problemi degli indirizzi cavalli di Troia, richiede quindi un’estrema attenzione e un’attenta validazione dei dati.

Fonte: IO.md

Scenarios tipici di attacco:

1. Buffer malevoli nelle primitive di I/O: Quando un processo utente chiama una primitiva di sistema passando un buffer, questo potrebbe:

Questo intervallo di indirizzi di memoria [buf, buf + quanti), potrebbe infatti trovarsi in una sezione di memoria alla quale lui non può accedere, ma il sistema sì.

Fonte: IO.md

2. Contesto di esecuzione confuso: Il driver esegue con privilegi di sistema ma deve operare su dati del processo utente:

Questi controlli, tediosi ma generalmente semplici, sono affetti da un’ulteriore complicazione: il driver gira infatti mentre in esecuzione c’è P2 e non P1. L’indirizzo privato fornitoci da P1, senza apporre le giuste precauzioni, verrebbe utilizzato nel contesto di P2, sovrascrivendone la memoria privata.

Fonte: IO.md

Meccanismi di protezione implementati:

1. Principio di non fiducia:

Lo standard che assumiamo è quello di non fidarci dell’utente. Sarà quindi necessario controllare e approvare i dati che l’utente ci fornisce.

Fonte: IO.md

2. Controlli di validazione sistematici: Per ogni indirizzo fornito dall’utente, il sistema deve verificare:

  1. Che l’indirizzo sia normalizzato;
  2. Che l’indirizzo sia mappato nel trie del processo;
  3. Nel caso di scritture di buffer, che si abbia accesso in scrittura a quest’ultimo
  4. Che buf + i non faccia wrap-around, con $0 \le i < quanti$
  5. Che [buf, buf+quanti) stia tutto nella stessa porzione di memoria

Fonte: IO.md

3. Restrizione alla memoria condivisa:

La soluzione più semplice, che è anche quella che generalmente adoperiamo, è quella di imporre la necessità che il buffer stia tutto nella parte condivisa, così da non scrivere nelle parti private di altri processi.

Fonte: IO.md

Protezione hardware delle strutture critiche:

1. Separazione dei livelli di privilegio:

Il livello di privilegio può essere cambiato solo in due modi:

Operazione Livello di privilegio
gate della IDT utente $\to$ sistema
Istruzione IRETQ sistema $\to$ utente

Fonte: Protezione.md

2. Controlli di accesso ai gate:

Se sta gestendo una interruzione software o int3, confronta il livello corrente con il campo DPL del gate. Se il livello corrente è meno privilegiato di DPL si genera una eccezione di protezione 13.

Fonte: Protezione.md

3. Protezione della pila sistema:

Il cambio di pila è necessario, è ha due motivazioni:

Fonte: Protezione.md

Funzione di controllo access(): Il sistema fornisce una funzione dedicata per la validazione:

extern "C" bool c_access(vaddr begin, natq dim, bool writeable, bool shared = true)

Questa funzione verifica che l’intervallo di memoria richiesto sia:

Implicazioni per la sicurezza: La gestione del problema del Cavallo di Troia è fondamentale per:

  1. Prevenire privilege escalation: impedire ai processi utente di ottenere accesso a memoria di sistema
  2. Mantenere l’isolamento: garantire che i processi non possano corrompere la memoria di altri processi
  3. Preservare l’integrità: proteggere le strutture dati critiche del sistema (IDT, GDT, tabelle di paginazione)

In sintesi, la protezione contro i Cavalli di Troia richiede una validazione sistematica e rigorosa di tutti gli indirizzi forniti dai processi utente, combinata con meccanismi hardware di protezione dei livelli di privilegio e separazione delle pile di sistema e utente.

Domanda 3.13 (answered)

Domanda: Cosa fa, dove e come si salta dopo carica_stato? Descriva il meccanismo di cambio di contesto.

Risposta: La funzione carica_stato è un meccanismo fondamentale per il cambio di contesto tra processi. Esaminiamo cosa fa, dove viene eseguita e come funziona il salto successivo.

Cosa fa carica_stato:

1. Ripristino dei registri: La funzione carica_stato ripristina tutti i registri del processore dal descrittore del processo puntato dalla variabile globale esecuzione:

Ciò significa che, carica_stato ripristinerà la pila di sistema del processo P2, e la successiva IRETQ ripristinerà proprio le istruzioni relative a quel processo, reinserendo il valore della pila di stack di P2.

Fonte: Sistemi Multiprocesso e Processi.md

2. Meccanismo di funzionamento:

carica_stato:
    ; Ripristina tutti i registri dal array contesto[N_REG] 
    ; del processo puntato da esecuzione
    ; effettua alcuni controlli:
    ;   - se cr3 non cambia non lo aggiorna (evita lo svuotamento del TLB)
    ;   - prima di cambirare %rsp, effettua una POPq del contenuto (%rip dell'istruzione dove andare finita la carica_stato), cambia %rsp e poi effettua una PUSHq di quel valore
    ;   - fa un controllo aggiuntivo per capire se il processo in realtà è stato abortito/terminato e nel caso chiama `distruggi_pila`
    ;
    ; Ricarica i vari registri: RAX, RBX, RCX, RDX, RSI, RDI, RBP, RSP, ...

Dal file Realizzazione Primitive.md:

// Per restituire r non possiamo fare return, ma scriviamo:
esecuzione->contesto[I_RAX] = r;
// Questo sovrascrive il contenuto del registro %rax che avevamo 
// salvato con la `salva_stato`, così da recuperarlo quando
// chiameremo la `carica_stato`

Dove si usa carica_stato:

1. Nelle routine delle primitive:

Le routine avranno quindi tutte lo stesso formato.

a_primitiva_i:
    CALL salva_stato
    CALL c_primitiva;
    CALL carica_stato
    IRETQ

Fonte: Realizzazione Primitive.md

2. Negli handler di interruzione: Dal file IO.md:

; Primitiva di sistema wfi() (waiting_for_interrupt)
a_wfi:
	; Stato del processo esterno riferito sopra
	CALL salva_stato
	CALL apic_send_EOI

	; Non abbiamo certezza di chi riprenderà l'esecuzione
	CALL schedulatore
	CALL carica_stato
	RET

3. Negli interrupt handler:

driver_td:
	call salva_stato
	call c_driver_td
    ; Aggiungiamo il segnale all'APIC
	call apic_send_EOI
	call carica_stato

Fonte: Delay e new.md

Dove si salta dopo carica_stato:

1. Sequenza normale in una primitiva:

a_primitiva:
    CALL salva_stato    ; Salva contesto processo corrente
    CALL c_primitiva    ; Esegue il corpo della primitiva (può cambiare esecuzione)
    CALL carica_stato   ; Ripristina contesto del processo in esecuzione
    IRETQ               ; ← SALTO: Ripristina le 5 long word e torna al processo

2. Il salto avviene tramite IRETQ: L’istruzione IRETQ che segue carica_stato ripristina:

  1. Salva in pila 5 long word [SS, SRSP, RFLAGS, CS, RIP]

Fonte: Protezione.md

Quindi IRETQ ripristina:

Meccanismo di cambio di contesto:

1. Principio fondamentale:

L’unico modo per transizionare da un processo ad un altro è tramite un gate della IDT.

Fonte: Sistemi Multiprocesso e Processi.md

2. Struttura dati del processo: Nel sistema, ogni processo ha un descrittore des_proc che contiene:

struct des_proc {
    natw id;                    // identificatore numerico del processo
    natw livello;              // livello di privilegio (LIV_UTENTE o LIV_SISTEMA)
    natl precedenza;           // precedenza nelle code dei processi
    vaddr punt_nucleo;         // indirizzo della base della pila sistema
    natq contesto[N_REG];      // copia dei registri generali del processore
    paddr cr3;                 // radice del TRIE del processo
    des_proc* puntatore;       // prossimo processo in coda
    void (*corpo)(natq);       // funzione da eseguire
    natq parametro;            // parametro della funzione
};

Fonte: Sistemi Multiprocesso e Processi.md

3. Sequenza completa del cambio contesto:

Fase 1 - Entrata nel gate:

  1. Si verifica un evento (interruzione, eccezione, INT)
  2. Il processore salva automaticamente le 5 long word in pila
  3. Si salta alla routine handler

Fase 2 - Salvataggio stato:

CALL salva_stato    ; Salva tutti i registri in esecuzione->contesto[N_REG]

Fase 3 - Corpo della routine:

// Il corpo della routine può cambiare la variabile esecuzione
esecuzione = nuovo_processo;  // Cambio di contesto!

Tutto il necessario per cambiare processo è quindi cambiare la variabile esecuzione all’interno del corpo della routine.

Fonte: Sistemi Multiprocesso e Processi.md

Fase 4 - Ripristino stato:

CALL carica_stato   ; Ripristina i registri dal nuovo processo

Fase 5 - Ritorno:

IRETQ              ; Salta al nuovo processo ripristinando le 5 long word

4. Gestione della variabile esecuzione:

Per capire a quale processo ci stiamo riferendo quando invochiamo salva_stato e carica_stato utilizziamo come già detto una variabile globale esecuzione.

Fonte: Sistemi Multiprocesso e Processi.md

Esempio pratico di cambio contesto:

Scenario: Il processo P1 chiama una primitiva che lo sospende e attiva P2.

  1. P1 esegue: INT $TIPO_PRIMITIVA
  2. Hardware salva: [SS_P1, RSP_P1, RFLAGS_P1, CS_P1, RIP_P1] nella pila sistema di P1
  3. salva_stato: Salva tutti i registri di P1 in P1->contesto[N_REG]
  4. Corpo primitiva: Cambia esecuzione da P1 a P2
  5. carica_stato: Ripristina tutti i registri da P2->contesto[N_REG]
  6. IRETQ: Ripristina [SS_P2, RSP_P2, RFLAGS_P2, CS_P2, RIP_P2] dalla pila sistema di P2

Risultato: Il processore ora esegue le istruzioni del processo P2 dal punto in cui era stato sospeso.

Dove salta esattamente: Dopo carica_stato + IRETQ, il processore salta a:

Il meccanismo garantisce un cambio di contesto atomico e trasparente tra i processi, mantenendo l’illusione che ogni processo abbia il controllo esclusivo del processore.

4. Eccezioni

Domanda 4.1 (answered)

Domanda: Qual è la differenza fondamentale tra interruzioni ed eccezioni in termini di quando possono essere sollevate durante l’esecuzione di un’istruzione?

Risposta: La differenza fondamentale tra interruzioni ed eccezioni riguarda il timing del loro sollevamento rispetto al ciclo di esecuzione delle istruzioni.

Interruzioni:

Quello che possiamo fare per supportare gli eventi di questa interfaccia è collegare fisicamente il bit della stampante alla CPU e aggiungere una $\mu$-istruzione che controlla il bit al termine di ogni istruzione.

Fonte: Interruzioni.md

Le interruzioni vengono controllate e accettate solo tra un’istruzione e la successiva. Il processore verifica la presenza di richieste di interruzione alla fine di ogni istruzione completata, quando il processore si trova in uno stato consistente.

Caratteristiche delle interruzioni:

Eccezioni:

Mentre le interruzioni possono accedere solo tra un’istruzione e la successiva, le eccezioni possono essere sollevate in un momento qualunque di un’istruzione (lettura, decodifica, esecuzione).

Fonte: Eccezioni.md

Le eccezioni possono essere sollevate durante qualsiasi fase dell’esecuzione di un’istruzione:

Classificazione delle eccezioni per timing: Dal file Eccezioni.md:

Tipo Quando viene generata Indirizzo salvato Gestione
Fault Durante l’esecuzione di un’istruzione Indirizzo dell’istruzione che stava eseguendo Permette la ri-esecuzione dell’istruzione dopo la correzione
Trap Tra l’esecuzione di un’istruzione e la successiva Indirizzo dell’istruzione successiva Comportamento simile alle interruzioni
Abort In qualsiasi momento - Errori gravi, spesso irreversibili

Implicazioni pratiche:

  1. State saving: Le eccezioni richiedono meccanismi più complessi per salvare lo stato del processore, dato che possono interrompere un’istruzione a metà
  2. Recovery: I Fault permettono di correggere il problema e riprovare l’istruzione che ha causato l’eccezione
  3. Sincronismo: Le eccezioni sono sempre sincrone rispetto al flusso di istruzioni, mentre le interruzioni sono asincrone

Esempio pratico:

Questa distinzione è fondamentale per capire come il processore gestisce gli eventi e mantiene la coerenza del sistema.

Domanda 4.2 (answered)

Domanda: Come funziona l’eccezione di debug int3 e come viene utilizzata dai debugger per implementare i breakpoint?

Risposta: L’eccezione di debug int3 è un meccanismo hardware fondamentale che permette ai debugger di controllare l’esecuzione dei programmi attraverso i breakpoint. È implementata tramite l’eccezione tipo 3 della IDT.

Caratteristiche dell’eccezione int3:

Classificazione:

Fonte: Eccezioni.md

L’int3 è classificato come un’eccezione di tipo Trap:

Tipo Quando viene generata Indirizzo salvato Gestione
Trap Tra l’esecuzione di un’istruzione e la successiva Indirizzo dell’istruzione successiva Comportamento simile alle interruzioni

Fonte: Eccezioni.md

Implementazione dei breakpoint:

1. Meccanismo base:

È grazie a questa che il debugger riesce a controllare il flusso del programma sul quale è eseguito. Quando il debugger inserisce un breakpoint in un indirizzo, quello che fa operativamente è sostituire il primo byte a quell’indirizzo con il valore 0xcc, salvando il byte significativo.

Fonte: Eccezioni.md

Il valore 0xcc corrisponde al codice macchina dell’istruzione int3 su architettura x86.

2. Ciclo di esecuzione del breakpoint:

Fase 1 - Attivazione del breakpoint:

Tramite il segnale di continue il debugger rilascia il controllo al programma, che eseguirà finché non farà la fetch dell’eccezione. Il controllo torna quindi al debugger, che opererà finché il programmatore non restituirà il controllo al programma.

Fonte: Eccezioni.md

Fase 2 - Gestione della transizione:

Prima di permettere al programmatore di agire sul codice, il debugger reinserisce il vecchio valore dove aveva salvato 0xcc, e setta il bit TF così da generare un’eccezione di single-step.

Fonte: Eccezioni.md

Fase 3 - Esecuzione dell’istruzione originale:

Il programma eseguirà quindi l’operazione dove era stato chiamato il breakpoint per poi dare controllo nuovamente al debugger, che reinserirà il valore 0xcc così da mantenere il breakpoint per le successive iterazioni. Il debugger resetta quindi TF e restituisce per l’ultima volta il controllo al flusso principale

Fonte: Eccezioni.md

Interazione con il flag TF (Trap Flag):

Il flag TF nell’RFLAGS abilita il single-step debugging:

Fonte: Eccezioni.md

Gestione hardware dell’eccezione:

Quando si verifica un’eccezione int3, il processore segue la stessa procedura delle altre eccezioni:

  1. Innanzitutto il processore si procura il tipo dell’interruzione
    • In caso di eccezione il tipo è implicito;

Fonte: Protezione.md

Esempio di utilizzo nel nostro sistema:

Dal contesto del debugger utilizzato nel corso:

Possiamo notare inoltre che il debugger è preimpostato per caricare i simboli di tutti e tre i moduli. È quindi possibile inserire breakpoint liberamente nel codice del modulo sistema, utente e io.

Fonte: Sistemi Multiprocesso e Processi.md

Vantaggi del meccanismo int3:

  1. Precisione: Permette di fermare l’esecuzione esattamente in un punto specifico
  2. Trasparenza: L’istruzione originale viene preservata e rieseguita correttamente
  3. Efficienza: Utilizza un’istruzione di un solo byte (0xcc)
  4. Atomicità: Il breakpoint è gestito completamente a livello hardware
  5. Persistenza: Il breakpoint rimane attivo per esecuzioni successive

Differenze con altre forme di debugging:

Limitazioni:

Il meccanismo int3 rappresenta quindi la base hardware fondamentale per tutti i moderni debugger, permettendo di implementare breakpoint efficienti e affidabili senza modificare sostanzialmente l’architettura del programma in esecuzione.

Domanda 4.3 (answered)

Domanda: Che fa la CPU quando rileva un’eccezione? Come fa la CPU a capire dove saltare?

Risposta: Quando la CPU rileva un’eccezione, attiva un meccanismo hardware ben definito che gestisce automaticamente il salto alla routine di gestione appropriata attraverso la IDT (Interrupt Descriptor Table).

Rilevamento delle eccezioni:

1. Natura delle eccezioni:

Le eccezioni, quando vengono sollevate, sono quindi gestite immediatamente attraverso routine.

Fonte: Eccezioni.md

Le eccezioni sono eventi sincroni che possono essere sollevati:

Mentre le interruzioni possono accedere solo tra un’istruzione e la successiva, le eccezioni possono essere sollevate in un momento qualunque di un’istruzione (lettura, decodifica, esecuzione).

Fonte: Eccezioni.md

2. Tipi di eccezioni predefiniti:

Le routine delle eccezioni sono anch’esse salvate nella IDT, in particolare nelle prime 32 entrate. I loro tipi sono fissi e impliciti, consultabili nel manuale del processore. Alcune eccezioni famose sono:

Fonte: Eccezioni.md

Meccanismo di salto attraverso la IDT:

1. Identificazione del tipo:

Quando il processore accede all’IDT accadono questi passaggi:

  1. Innanzitutto il processore si procura il tipo dell’interruzione
    • In caso di eccezione il tipo è implicito;
    • In caso di interruzione esterna, riceve il tipo dall’APIC;
    • In caso di interruzione software è l’argomento specificato nell’istruzione INT $tipo.

Fonte: Protezione.md

2. Accesso alla IDT:

Affinché tutto questo funzioni, la CPU ha un suo registro interno chiamato IDTR (Interrupt Descriptor Table Register) che ha salvato l’indirizzo della IDT salvata in memoria. La IDT è una tabella che ha per ogni riga delle informazioni che vedremo meglio nel dettaglio nella sezione dedicata alla Protezione. Alcune informazioni sono:

Fonte: Interruzioni.md

3. Controlli di sicurezza:

  1. Verifica se il bit P associato al tipo è zero, generando un’eccezione di gate non presente 11 in caso positivo, negli altri casi procede.

  2. Se sta gestendo una interruzione software o int3, confronta il livello corrente con il campo DPL del gate. Se il livello corrente è meno privilegiato di DPL si genera una eccezione di protezione 13.

  3. Altrimenti, confronta CS con L. Se L è inferiore, si genera ancora un’eccezione di protezione 13.

Fonte: Protezione.md

Salvataggio automatico dello stato:

1. Cambio di pila e salvataggio:

  1. Negli altri casi, il processore salva in un registro di appoggio (chiamiamolo SRSP) il contenuto corrente di RSP

  2. Se CS è diverso da L esegue un cambio di pila (pila sistema/utente nel nostro caso), caricando un nuovo valore in RSP

  3. Salva in pila 5 long word. In ordine:

    • [0] SS: 1 long word non significativa (rimasuglio della segmentazione, …)
    • [1] SRSP: pila salvata al passo 5. Nel caso di cambio pila è quella utente, altrimenti punta alla pila sistema stessa
    • [2] RFLAGS: registro dei flag
    • [3] CS: vecchio valore del CS da ripristinare successivamente
    • [4] RIP: indirizzo della prima istruzione da eseguire all’uscita del gate. Nel caso di interruzioni software INT $tipo questo contiene l’istruzione immediatamente successiva

Fonte: Protezione.md

2. Configurazione dei flag:

  1. Il processore poi azzera:
    • TF in ogni caso;
    • IF solo se il gate è di tipo Interrupt.
  2. Salta infine all’indirizzo della routine puntata dal gate.

Fonte: Protezione.md

Classificazione delle eccezioni per gestione:

Le eccezioni vengono classificate in base al momento e alle modalità di gestione:

Tipo Quando viene generata Indirizzo salvato Scopo/Effetto
Fault Durante l’esecuzione di un’istruzione Indirizzo dell’istruzione che stava eseguendo La routine dovrebbe sistemare il problema per poter rieseguire l’istruzione
Trap Tra l’esecuzione di un’istruzione e la successiva Indirizzo dell’istruzione successiva -
Abort In qualsiasi momento - Gestisce errori particolarmente gravi, tipicamente causa lo spegnimento del calcolatore

Fonte: Eccezioni.md

Esempio pratico - Divisione per zero:

#include <libce.h>

extern "C" void a_divPerZero();
extern "C" void c_divPerZero(natq rip) {
    printf("Divisione per 0, all'indirizzo %lx!\n", rip);
}

int main() {
    int b = 0;
    gate_init(0, a_divPerZero);  // Associa tipo 0 alla routine custom
    /*
    *  Inizializzo la riga 0 della IDT(DivisionPerZeroFault)
    *  con la mia funzione
    */
    int a = 3 / b;  // Genera eccezione tipo 0
}

Processo completo:

  1. Rilevamento: La CPU rileva la divisione per zero durante l’esecuzione
  2. Tipo implicito: Automaticamente identifica il tipo 0 (divisione per zero)
  3. Accesso IDT: Usa IDTR per accedere alla entry 0 della IDT
  4. Controlli: Verifica presenza del gate e privilegi
  5. Salvataggio: Salva automaticamente stato del processore in pila
  6. Salto: Salta alla routine a_divPerZero specificata nel gate
  7. Gestione: Esegue la routine di gestione dell’eccezione

In sintesi, la CPU gestisce le eccezioni attraverso un meccanismo hardware completamente automatico che garantisce transizioni sicure e controllate verso le routine di gestione appropriate, utilizzando la IDT come tabella di dispatch e preservando automaticamente lo stato del processore per un eventuale recupero.

Domanda 4.4 (answered)

Domanda: Cosa succede se ho un page fault su una istruzione LOAD? Come viene gestita questa situazione?

Risposta: Un page fault su un’istruzione LOAD rappresenta una delle situazioni più comuni e critiche nella gestione della memoria virtuale, richiedendo un meccanismo sofisticato di gestione delle eccezioni di tipo Fault.

Natura del page fault durante una LOAD:

1. Classificazione dell’eccezione: Un page fault è un’eccezione di tipo Fault, il che significa:

Tipo Quando viene generata Indirizzo salvato Scopo/Effetto
Fault Durante l’esecuzione di un’istruzione Indirizzo dell’istruzione che stava eseguendo La routine dovrebbe sistemare il problema per poter rieseguire l’istruzione

Fonte: Eccezioni.md

2. Momento del sollevamento:

Mentre le interruzioni possono accedere solo tra un’istruzione e la successiva, le eccezioni possono essere sollevate in un momento qualunque di un’istruzione (lettura, decodifica, esecuzione).

Fonte: Eccezioni.md

Meccanismo di rilevamento del page fault:

1. Controllo del bit P durante la traduzione:

Se uno qualsiasi dei bit P incontrati durante la traduzione vale 0, la Trie-MMU smette di tradurre e solleva un’eccezione di page fault.

Fonte: Paginazione.md

2. Interruzione del processo di traduzione: Durante un’istruzione LOAD, la MMU esegue il table-walk per tradurre l’indirizzo virtuale:

Salvataggio dello stato durante il page fault:

1. Informazioni salvate automaticamente:

Quando si accede ad un gate della IDT (tramite interruzione, eccezione o int), sappiamo che vengono già salvate delle informazioni (5 long word):

Fonte: Domande e Risposte.md

2. Indirizzo dell’istruzione che ha causato il fault: Per le eccezioni di tipo Fault, RIP contiene l’indirizzo dell’istruzione che ha generato l’eccezione, non dell’istruzione successiva. Questo permette di riprovare l’istruzione dopo aver risolto il problema.

Gestione del page fault da parte del kernel:

1. Routine di gestione: Il kernel ha una routine dedicata per gestire i page fault, registrata nella entry 14 della IDT.

2. Casi possibili:

3. Strategia di recovery: Per un Fault, la strategia è sempre quella di:

  1. Identificare la causa del page fault
  2. Risolvere il problema (caricare la pagina, aggiornare i permessi, etc.)
  3. Riprovare l’istruzione originale

Esempio di gestione:

extern "C" void a_page_fault();
extern "C" void c_page_fault(natq rip, natq error_code) {
    // Ottieni l'indirizzo che ha causato il fault dal registro CR2
    vaddr fault_addr = readCR2();
    
    if (error_code & 0x1) {
        // Violazione di protezione
        handle_protection_violation(fault_addr, rip);
    } else {
        // Pagina non presente - carica la pagina
        if (load_page_from_swap(fault_addr)) {
            // Pagina caricata con successo, l'istruzione verrà riprovata
            return;
        } else {
            // Errore irrecuperabile
            terminate_process();
        }
    }
}

Interazione con il TLB:

1. Invalidazione necessaria:

Un esempio di TLB a due vie può essere il seguente: […] Questo processo è obbligatorio nei cambi di contesto, in quanto le traduzioni di P1 non hanno senso per P2.

Fonte: Paginazione.md

2. Aggiornamento dopo recovery: Dopo aver risolto il page fault e caricato la pagina:

Ripristino dell’esecuzione:

1. Ritorno con IRETQ: Dopo aver gestito il page fault, la routine termina con IRETQ, che:

2. Successo del recovery: Se il page fault è stato gestito correttamente:

Considerazioni prestazionali:

I page fault sono eventi costosi perché richiedono:

Tuttavia, rappresentano un meccanismo fondamentale per:

In sintesi, un page fault su un’istruzione LOAD attiva un meccanismo sofisticato di gestione delle eccezioni che permette al sistema operativo di gestire dinamicamente la memoria virtuale, mantenendo l’illusione di uno spazio di indirizzamento continuo e illimitato per i processi utente.

5. Protezione

Domanda 5.1 (answered)

Domanda: Come funzionano i livelli di privilegio nei processori Intel? Quali operazioni sono vietate a livello utente?

Risposta: I livelli di privilegio nei processori Intel x86 sono un meccanismo hardware fondamentale per implementare la protezione e garantire la sicurezza del sistema.

Nel nostro sistema utilizziamo solo due livelli di privilegio:

Fonte: Protezione.md

Il livello di privilegio corrente è memorizzato nel registro CS (Code Selector) e determina quale contesto di esecuzione è attivo.

Il processore distingue tra due contesti principali:

  1. Contesto Sistema:
    • Ha accesso completo all’hardware
    • Può eseguire tutte le istruzioni privilegiate
    • Può accedere a tutte le aree di memoria
  2. Contesto Utente:
    • Accesso limitato alle risorse hardware
    • Molte istruzioni sono vietate
    • Accesso limitato alla memoria

L’idea generale di questo sistema è la seguente:

  1. All’accensione, tramite il bootstrap, si inizializza il processore a livello sistema
  2. Quando viene inizializzato un job si passa a livello utente
  3. Quando viene generata un’interruzione esterna, si torna al livello sistema
  4. Gestita l’interruzione esterna, si torna al job nel livello utente

Fonte: Protezione.md

Le principali operazioni vietate quando il processore opera in contesto utente sono:

Andremo quindi a vietare le istruzioni di IN, OUT, CLI, STI per il contesto utente, permettendole solamente quando ci si trova nel contesto sistema.

Fonte: Protezione.md

Controllo delle Interruzioni

Nei processori Intel vi è un’associazione tra IN e OUT ai comandi CLI e STI. Se ponessimo il LIV_UTENTE, forniremmo l’accesso all’utente anche a queste istruzioni, cosa che abbiamo già visto non va fatta.

Fonte: IO.md

Per non permettere la modifica di IDT da parte dell’utente l’istruzione LIDTR è anch’essa vietata nel contesto utente.

Fonte: Protezione.md

I processi utente non possono accedere direttamente alle aree di memoria riservate al sistema:

Entrambi i registri sono scrivibili solo da livello sistema.

Fonte: Paginazione.md

Il cambio di livello di privilegio può avvenire solo in modi controllati:

Il livello di privilegio può essere cambiato solo in due modi:

Operazione Livello di privilegio
gate della IDT utente → sistema
Istruzione IRETQ sistema → utente

Fonte: Protezione.md

Il passaggio da utente a sistema avviene attraverso i gate della IDT tramite:

IL passaggio da sistema a utente avviene esclusivamente tramite l’istruzione IRETQ alla fine delle routine di sistema.

Quando il processore incontra un’istruzione privilegiata in contesto utente, genera un’eccezione di protezione (tipo 13):

Il sistema sul quale lavoriamo è progettato affinché qualsiasi eccezione venga sollevata in modalità utente, restituisce il controllo al modulo sistema, il quale termina forzatamente il processo e invia alcuni messaggi sul log.

Fonte: Sistemi Multiprocesso e Processi.md

Per permettere ai processi utente di accedere ai servizi del sistema operativo in modo controllato, vengono utilizzate le primitive di sistema:

Permetteremo all’utente di utilizzare una determinata eccezione (non modificabile nella memoria), salvando in un registro quale routine si vuole chiamare. La Intel ha adottato un sistema diverso, introducendo un nuovo operando assembler INT $tipo che fa da gate per chiamare la routine (primitiva di sistema) e passare in modalità sistema.

Fonte: Protezione.md

Questo meccanismo garantisce che:

  1. I processi utente non possano interferire con il sistema
  2. L’accesso alle risorse hardware sia mediato dal kernel
  3. La stabilità e sicurezza del sistema siano preservate

I livelli di privilegio rappresentano quindi una barriera hardware fondamentale per l’implementazione della sicurezza nei sistemi operativi moderni.

Domanda 5.2 (answered)

Domanda: Cosa sono M1 e M2? Come viene controllato l’accesso alla memoria per livello di privilegio?

Risposta: M1 e M2 rappresentano le due macro-zone in cui è divisa la memoria fisica per implementare la protezione hardware tra contesto sistema e contesto utente.

Definizione di M1 e M2:

Da ora in poi chiameremo M1 la parte di memoria ad indirizzi superiori al limite (system-only), e M2 la rimanente. Il registro contenente l’indirizzo di separazione viene inizializzato tramite il programma di bootstrap, lo stesso che carica IDT e il corpo delle varie routine e strutture dati

Fonte: Protezione.md

Caratteristiche delle zone:

M1 (Memoria Sistema):

In tutto questo contesto va però ridefinita la porzione di memoria concessa all’utente. Se infatti avesse a disposizione tutta la memoria l’utente potrebbe:

Fonte: Protezione.md

M2 (Memoria Utente/Sistema):

Controllo dell’accesso per livello di privilegio:

1. Meccanismo hardware di verifica:

Ogni qualvolta che il processore effettuerà un accesso in memoria, prima controllerà il contesto e, nel caso fosse nel contesto utente, controllerà che l’indirizzo desiderato sia maggiore o uguale a quello contenuto nel registro.

Fonte: Protezione.md

2. Implementazione con registri limite: Nel sistema con paginazione si utilizzano i registri LINF e LSUP:

Per vietare all’utente l’accesso alle porzioni di M2 di processi diversi, si inseriscono nella CPU due registri, LINF e LSUP, che hanno come compito quello di contenere gli indirizzi dell’inizio e della fine della porzione di memoria virtuale del processo in esecuzione. Entrambi i registri sono scrivibili solo da livello sistema.

Fonte: Paginazione.md

3. Controllo degli accessi:

Quando la CPU lavora in modalità utente, deve controllare che gli accessi siano in indirizzi compresi nell’intervallo $\Bigl[$LINF, LSUP$\Bigr)$. In caso di accessi out-of-bound si genererà invece un’eccezione di protezione 13.

Fonte: Paginazione.md

Architettura della memoria virtuale:

Con l’introduzione della paginazione, la separazione diventa più sofisticata:

La parte che va dall’indirizzo 0x0000 0000 0000 0000 all’indirizzo 0x0000 7fff ffff ffff è dedicata al sistema, ed ha quindi settato il bit U/S = 0, mentre la parte che va da 0xffff 8000 0000 0000 a 0xffff ffff ffff ffff è dedicata all’utente, ed ha quindi settato il bit U/S = 1.

Fonte: Memoria Virtuale nel Nucleo.md

Organizzazione di M1 nella memoria fisica:

La parte M1 della memoria fisica è così organizzata:

Fonte: Memoria Virtuale nel Nucleo.md

Vantaggi del sistema M1/M2:

  1. Protezione hardware: Impossibilità per i processi utente di corrompere il sistema
  2. Isolamento: Separazione netta tra risorse di sistema e utente
  3. Sicurezza: Prevenzione di modifiche non autorizzate alle strutture critiche
  4. Flessibilità: M2 può essere gestita dinamicamente per i processi

In sintesi, M1 e M2 rappresentano una separazione fisica fondamentale che, combinata con i livelli di privilegio e la paginazione, garantisce l’integrità e la sicurezza del sistema operativo.

Domanda 5.3 (answered)

Domanda: Come è fatto un gate della IDT? Da dove viene preso il valore del nuovo %rsp se si cambia pila mentre si attraversa un gate?

Risposta: I gate della IDT sono strutture hardware fondamentali per la gestione delle interruzioni e il cambio di contesto nei processori Intel, contenenti informazioni cruciali per la protezione e la transizione tra livelli di privilegio.

Struttura di un gate della IDT:

Ogni gate della IDT occupa 16Byte e contiene le segueni informazioni:

Fonte: Protezione.md

Funzione dei campi principali:

Campo DPL (Descriptor Privilege Level):

Può vietare l’utilizzo di alcuni gate attraverso l’istruzione INT generando un’eccezione di protezione 13. I programmatori di sistema possono settarlo come:

Fonte: Protezione.md

Meccanismo di attraversamento del gate: Quando il processore attraversa un gate della IDT, segue una sequenza precisa:

  1. Innanzitutto il processore si procura il tipo dell’interruzione
  2. Verifica se il bit P associato al tipo è zero, generando un’eccezione di gate non presente 11 in caso positivo
  3. Se sta gestendo una interruzione software o int3, confronta il livello corrente con il campo DPL del gate.
  4. Altrimenti, confronta CS con L. Se L è inferiore, si genera ancora un’eccezione di protezione 13.

Fonte: Protezione.md

Cambio di pila e origine del nuovo %rsp:

Necessità del cambio pila:

Il cambio di pila è necessario, è ha due motivazioni:

Fonte: Protezione.md

Meccanismo del cambio pila:

  1. Negli altri casi, il processore salva in un registro di appoggio (chiamiamolo SRSP) il contenuto corrente di RSP
  2. Se CS è diverso da L esegue un cambio di pila (pila sistema/utente nel nostro caso), caricando un nuovo valore in RSP

Origine del nuovo %rsp - Il TSS:

Nei primi processori intel ogni job aveva un proprio segmento di un registro chiamato TSS, che indicava la pila a disposizione del job. Per identificare la pila sistema si accedeva prima ad un’altro registro, TR (Task Register), che indicava quale segmento era associato a quel job.

Fonte: Protezione.md

Cosa viene salvato in pila:

  1. Salva in pila 5 long word. In ordine:
    • [0] SS: 1 long word non significativa (rimasuglio della segmentazione, …)
    • [1] SRSP: pila salvata al passo 5. Nel caso di cambio pila è quella utente, altrimenti punta alla pila sistema stessa
    • [2] RFLAGS: registro dei flag
    • [3] CS: vecchio valore del CS da ripristinare successivamente
    • [4] RIP: indirizzo della prima istruzione da eseguire all’uscita del gate.

Fonte: Protezione.md

Esempio pratico nella creazione di processi: Nel sistema studiato, la pila sistema viene preparata durante la creazione del processo:

pl[-6] = int_cast<natq>(f);		      // RIP (codice sistema)
pl[-5] = SEL_CODICE_SISTEMA;          // CS (codice sistema)
pl[-4] = BIT_IF;  	        	      // RFLAGS (abilitiamo le interruzioni)
pl[-3] = fin_sis_p - sizeof(natq);    // RSP (primo elemento della pila)
pl[-2] = 0;			                  // SS
pl[-1] = 0;			                  // ind. rit.

Fonte: Memoria Virtuale nel Nucleo.md

Protezione e sicurezza:

Le interruzioni di protezione sono progetatte per poter solamente mantenere o alzare il livello di privilegio.

In particolare, è bene che l’utente non possa modificare il valore salvato di CS.

Fonte: Protezione.md

Configurazione della IDT:

La IDT viene inizializzata tramite il programma di bootstrap, in particolare utilizzando l’istruzione LIDTR che carica l’indirizzo della IDT nel registro IDTR che il processore utilizza per accedere ala tabella e allocando IDT nella memoria M1. Per non permettere la modifica di IDT da parte dell’utente l’istruzione LIDTR è anch’essa vietata nel contesto utente.

Fonte: Protezione.md

In sintesi, i gate della IDT sono meccanismi sofisticati che garantiscono transizioni sicure tra contesti, mentre il nuovo %rsp proveniva dal TSS (Task State Segment) che contiene la pila sistema dedicata a ciascun processo, assicurando che le informazioni critiche siano protette dalla corruzione da parte del codice utente. Con l’introduzione della paginazione, la base della pila sistema si trova per ogni processo all’indirizzo virtuale fin_sis_p, e di conseguenza il nuovo valore di %rsp dopo il cambio pila sarà fin_sis_p - 5 * sizeof(natq).

Domanda 5.4

Domanda: Perché è necessario il cambio di pila negli attraversamenti di gate? Come funziona?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 5.5

Domanda: Come funziona l’istruzione IRETQ? Quali controlli di sicurezza effettua?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 5.6

Domanda: Perché si è resa necessaria l’introduzione della protezione nei sistemi di calcolo? Faccia riferimento all’evoluzione dai sistemi batch ai sistemi multiprogrammati.

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 5.7

Domanda: Quali problemi sorgerebbero se due job diversi potessero accedere contemporaneamente alle stesse periferiche senza un sistema di protezione?

Risposta: [La risposta verrà aggiunta quando richiesta]

6. Paginazione e Memoria Virtuale

Domanda 6.1

Domanda: Spiega il concetto di memoria virtuale e paginazione. Quali sono i vantaggi della suddivisione della memoria in pagine e frame?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.2 (answered)

Domanda: Cosa sono i registri LINF e LSUP? Quali problemi presentano nella gestione della memoria?

Risposta: I registri LINF e LSUP sono una soluzione hardware per implementare la protezione della memoria nei sistemi multi-processo, precedente alla paginazione moderna.

Funzione dei registri:

Per vietare all’utente l’accesso alle porzioni di M2 di processi diversi, si inseriscono nella CPU due registri, LINF e LSUP, che hanno come compito quello di contenere gli indirizzi dell’inizio e della fine della porzione di memoria virtuale del processo in esecuzione. Entrambi i registri sono scrivibili solo da livello sistema.

Fonte: Paginazione.md

Meccanismo di protezione:

Quando la CPU lavora in modalità utente, deve controllare che gli accessi siano in indirizzi compresi nell’intervallo $\Bigl[$LINF, LSUP$\Bigr)$. In caso di accessi out-of-bound si genererà invece un’eccezione di protezione 13.

Gestione durante il cambio processo:

Per permettere questa configurazione LINF non contiene più il primo indirizzo di M2, ma bensì quello della prima locazione appartenente al processo in esecuzione. Entrambi i registri devono quindi avere una posizione nel vettore contesto dei descrittori di processo, ovvero I_LINF e I_LSUP:

Traduzione degli indirizzi:

Da adesso in poi, la CPU interpreta ogni indirizzo x come LINF + x. In questo modo ogni indirizzo “assoluto” di un processo, adesso indica semplicemente l’offset da LINF di quel processo.

Problemi principali:

1. Problema di rilocazione del codice:

Il primo risiede nel capire dove salvare la sezione .text di ogni processo. Infatti, a differenza della memoria unica, dove la sezione .text aveva un indirizzo costante dove essere salvata (LINF), nel caso di memorie multiple il collegatore, si troverà indirizzi di partenza variabili a seconda dello stato del sistema.

Le soluzioni includono:

2. Problema degli indirizzi assoluti:

Un secondo problema risiede nel fatto che i processi potrebbero utilizzare indirizzi assoluti per salvare oggetti in memoria.

Ipotizziamo di avere un processo P1 che salva un indirizzo assoluto nella sua partizione. Questo processo viene poi rimosso e rilocato in un’altra, diversa dalla prima. A questo punto l’indirizzo assoluto che era utilizzato non sarà più disponibile, in quanto si riferisce ad una partizione adesso out-of-bound.

Vincolo forte:

Se un processo è locato in una determinata partizione della memoria, nel caso di scarica e carica, dovrà sempre essere rilocato nello stessa posizione.

3. Frammentazione esterna:

Permane comunque il problema della frammentazione esterna.

4. Memoria condivisa limitata:

Il terzo problema risiede sulla mancanza di una memoria condivisa, possibile con questo hardware, solamente tra processi in partizioni adiacenti.

Superamento: Questi problemi hanno portato allo sviluppo della paginazione, che risolve la frammentazione esterna e permette maggiore flessibilità nella gestione della memoria virtuale, eliminando completamente la necessità dei registri LINF e LSUP.

Domanda 6.3

Domanda: Qual è il problema della frammentazione esterna e come la paginazione lo risolve?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.4

Domanda: Perché è necessario che gli indirizzi Intel x86-64 siano normalizzati? Cosa significa “buco” nella memoria virtuale?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.5 (answered)

Domanda: Cosa sono le tabelle di livello nel Trie-MMU? Come sono organizzate e indicizzate?

Risposta: Le tabelle di livello nel Trie-MMU costituiscono l’implementazione hardware della memoria virtuale attraverso una struttura ad albero (trie) che sostituisce la Super-MMU teorica, riducendo drasticamente i requisiti di memoria.

Problema della Super-MMU:

La Super-MMU teorica richiederebbe dimensioni enormi:

La stragrande maggioranza dei programmi ha bisogno solo di una piccola frazione dei $2^{48}$Byte disponibili nella memoria virtuale, ed è solo di quella porzione che vorremmo contenere le informazioni.

Fonte: Paginazione.md

La tabella di corrisponendza di ogni processo deve avere una entrata per ognuna di queste pagine. […] per un totale nel peggiore dei casi di 47bit arrotondabili in 6Byte. […] che per le 64Gi pagine comporta un totale di 512GiB.

Fonte: Paginazione.md

Struttura del Trie-MMU:

Organizzazione gerarchica a 4 livelli:

In particolare il numero di pagina è composto da 36bit, raggrupabili in 4 gruppi di 9bit. Ogni nodo del bitwise trie conterrà dunque una tabella di $2^9 = 512$ entrate con puntatori al nodo successivo.

Fonte: Paginazione.md

Per convenzione ogni livello dell’albero viene numerato da 4 a 1 (livello delle foglie), in modo di poter parlare di tabelle di livello x.

Fonte: Paginazione.md

Indicizzazione e table-walk:

Dal file Paginazione.md:

Ipotizziamo che il nostro trie si trovi a dover tradurre l’indirizzo virtuale v = (000 777 000 777 1234)_8, che ha quindi come numero di pagina: (000 777 000 777)_8.

I primi 9bit sono $(000)_8$, perciò verrà utilizzata l’entrata di indice 0 del livello 4, recuperandone il contenuto. Questo contenuto rappresenta l’indirizzo dove si trova la tabella da interpretare come di livello 3.

Il processo continua attraversando i 4 livelli usando i successivi gruppi di 9 bit.

Organizzazione delle tabelle:

1. Tabelle di livello 4, 3, 2 (descrittori di tabella):

I descrittori di livello 2, 3 e 4 hanno invece la seguente forma:

| padding (63-53) | Indirizzo tabella di livello $i$ - 1 | padding (11 - 8) | PS | - | A | - | - | U/S | R/W | P | Ciascuna contiene 512 entrate.

Fonte: Paginazione.md

Questi descrittori contengono:

2. Tabelle di livello 1 (descrittori di pagina):

Da adesso chiameremo queste entrate descrittori di pagina virtuale o descrittori di livello 1.

padding (63-53) numero di frame padding (11 - 7) D A PCD PWT U/S R/W P

Fonte: Paginazione.md

Contengono:

Gestione della memoria efficiente:

Allocazione dinamica:

Con la Trie-MMU possiamo non istanziare tutte le entrate immediatamente. Per fare ciò poniamo semplicemente P = 0 nelle righe tabelle di livello 2, 3 o 4 che si riferiscono a indirizzi mai utilizzati.

Fonte: Paginazione.md

Vantaggi dell’approccio:

Se ad esempio un processo non usa nessun indirizzo il cui numero di pagina inizi con $(777)8$, il _trie di questo processo non ha bisogno di tutto il sottoalbero di quel nodo, ed eviterà quindi di allocarlo.

Fonte: Paginazione.md

Regioni e sottoregioni:

Definizione delle regioni:

Ogni entrata di una tabella di livello $i$, con $1 \le i \le 4$, sarà responsabile della traduzione di una regione naturale di livello $i -1$.

Ogni tabella di livello $i$ sarà responsabile nella sua interezza della traduzione di una regione naturale dello stesso livello $i$.

Fonte: Paginazione.md

Dimensioni delle regioni:

Dal file Paginazione.md:

In generale una regione di livello $j$, con $0\le j\le 4$, è grande $2^{9j + 12}$ byte.

Implementazione hardware:

Posizionamento in memoria fisica:

Nella MMU non funziona così, ma le tabelle devono essere memorizzate nella memoria fisica. Infatti anche le tabelle sono allineate a 4KiB, quindi perfettamente inseribili nei frame di M2.

Fonte: Paginazione.md

Gestione del registro CR3:

Il registro %cr3 della MMU contiene semplicemente il numero di frame della tabella radice del trie corrente. La MMU si limita quindi a realizzare in hardware il table-walk, nella RAM.

Fonte: Paginazione.md

Condivisione della memoria:

Meccanismo di condivisione:

Questa struttura ci permette di non dovere allocare più volte in uno stesso trie una zona di memoria condivisa. Per condividere la memoria sarà sufficente far puntare allo stesso nodo i trie di due processi distinti, ovvero inserire nella tabella di livello 4 lo stesso indirizzo allo stesso offset, così da puntare alla stessa tabella di livello 3.

Fonte: Paginazione.md

Controlli durante la traduzione:

Durante il table-walk, la MMU esegue controlli su tutti i livelli:

Fonte: Paginazione.md

Conclusioni:

Le tabelle di livello nel Trie-MMU rappresentano un’elegante soluzione ingegneristica che:

  1. Riduce drasticamente i requisiti di memoria rispetto alla Super-MMU
  2. Mantiene le prestazioni attraverso allocazione dinamica degli alberi
  3. Facilita la condivisione di memoria tra processi
  4. Supporta pagine di diverse dimensioni tramite il bit PS
  5. Implementa controlli di protezione a tutti i livelli dell’albero

Questa architettura è alla base dei moderni sistemi di memoria virtuale e rappresenta un perfetto equilibrio tra efficienza, flessibilità e semplicità implementativa.

Domanda 6.6

Domanda: Evidenzia la differenza tra indirizzo virtuale e indirizzo fisico, ed esponi come funziona il table-walk nella traduzione degli indirizzi?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.7

Domanda: Qual è la differenza tra descrittori di pagina virtuale e descrittori di tabella?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.8

Domanda: Cos’è e com’è implementata la finestra sulla memoria fisica? Spieghi perché sono necessarie nel kernel?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.9 (answered)

Domanda: Spiega il funzionamento del TLB (Translation Lookaside Buffer). Perché è necessario per le prestazioni?

Risposta: Il TLB (Translation Lookaside Buffer) è una cache hardware specializzata che memorizza le traduzioni di indirizzi virtuali in indirizzi fisici utilizzate più recentemente, rappresentando un componente fondamentale per le prestazioni dei sistemi con memoria virtuale.

Problema delle prestazioni senza TLB:

Dal file Paginazione.md:

Introducendo la MMU, per ogni accesso in memoria da parte del software, accediamo ad un minimo di 4 tabelle per recuperare l’indirizzo fisico al quale successivamente accedere. Se consideriamo che la MMU deve aggiornare i bit A e D, possiamo arrivare a 8 accessi o persino 12 nei casi peggiori. Ciò riguarda anche gli accessi in cache.

Tutto questo processo non fa altro che rallentare la nostra CPU.

Soluzione TLB:

Inseriamo quindi una cache alla MMU chiamata TLB (Translation Lookaside Buffer).

Fonte: Paginazione.md

Funzionamento del TLB:

1. Scopo e meccanismo base:

Lo scopo della TLB è di ricordare le traduzioni utilizzate più recentemente, dove per traduzioni intendiamo ciò che è contenuto nei descrittori di livello 1, insieme alle informazioni accessorie.

Fonte: Paginazione.md

2. Processo di consultazione:

Quando MMU accede alla memoria tramite un’indirizzo virtuale, può quindi salvare nel TLB la sua traduzione. Agli accessi successivi si controllerà prima se in TLB è già presente il descrittore che si sta cercando, altrimenti ci si comporta come descritto fin’ora, tramite table-walk.

Fonte: Paginazione.md

Architettura del TLB:

Struttura hardware:

Dal file Paginazione.md:

Un esempio di TLB a due vie può essere il seguente:

Figura 1: V rappresenta l’indirizzo virtuale, F rappresenta l’indirizzo fisico.

Il TLB è organizzato come una cache associativa che contiene:

Ottimizzazioni di spazio:

Per ottimizzare lo spazio, all’interno dei dati nel TBL non sono salvate alcune informazioni:

Fonte: Paginazione.md

Gestione del TLB:

1. Svuotamento nei cambi di contesto:

La TLB, per struttura, è poco accessibile da software, tuttavia ne è permesso lo svuotamento. Questo processo è obbligatorio nei cambi di contesto, in quanto le traduzioni di P1 non hanno senso per P2.

Fonte: Paginazione.md

2. Automatismo hardware:

Nei processori Intel questo svuotamento avviene in automatico quando viene scritto %cr3, anche se viene cambiato in se stesso. (MOV %cr3, %cr3)

Fonte: Paginazione.md

Problemi specifici del TLB:

1. Gestione del bit A (Accessed):

Il bit A viene settato durante il table-walk, diventa quindi un problema azzerarlo via software. Infatti, se l’indirizzo è presente nel TLB, non viene rieseguito l’accesso al trie. In questo caso la soluzione è quella di azzerare le righe corrispondenti nel TLB prima di effettuare gli accessi che modificano A.

Fonte: Paginazione.md

2. Gestione del bit D (Dirty):

Il bit D deve essere settato solo quando effettuiamo un accesso in scrittura. Nel caso in cui effettuiamo un accesso in lettura tramite table-walk (che non setta D) a un indirizzo, lo salveremo nel TLB. A questo punto se effettuiamo un accesso in scrittura allo stesso indirizzo, dovremmo settare D nel trie, ma non vi accediamo mai in quanto si trova nella TLB.

Fonte: Paginazione.md

Soluzione per il bit D:

Settare quello nella TLB è completamente inefficace per il software poiché non solo è per lui inaccessibile, ma il contenuto stesso del TLB è volatile, in quanto è una cache, quindi ogni riga può essere soggetta a sovrascritture. È necessario quindi effettuare un table-walk per sovrascrivere il bit D. Il modo per farlo è non consultare la TLB negli accessi in scrittura di frame che avevano D = 0.

Fonte: Paginazione.md

TLB per pagine di diverse dimensioni:

Problema delle pagine grandi:

Quando effettuiamo una traduzione, non possiamo saperne a priori le dimensioni. Infatti questa informazione sarà accessibile solo quando arriveremo al livello 1, guardando il bit PS.

Fonte: Paginazione.md

Evoluzione delle soluzioni:

Nei primi processori, gli accessi a pagine più grandi dei 4KiB occupavano più righe del TLB. Ad esempio pagine da 2MB ne occupavano ben 512 righe.

Fonte: Paginazione.md

Soluzione moderna:

La soluzione moderna a questo problema è quella di avere un TLB per ogni dimensione. La traduzione verrà quindi cercata in parallelo in ciascuno dei TLB, come nel caso di TLB a più vie, e verrà selezionata solamente quella desiderata.

Fonte: Paginazione.md

Funzioni di controllo del TLB:

Invalidazione selettiva:

Dal file Paginazione.md:

Esiste anche la funzione invalida_entrata_TLB(v) che serve a invalidare la traduzione associata al vaddr v nel TLB nel caso ne stesse conservando una copia. Per invalidare l’intero TLB si può utilizzare invalida_TLB(), che nei processori Intel è equivalente a loadCR3(read(CR3)).

Necessità per le prestazioni:

1. Eliminazione dell’overhead: Il TLB riduce drasticamente il numero di accessi alla memoria:

2. Sfruttamento della località: Il TLB beneficia della località temporale degli accessi alla memoria:

3. Parallelismo efficiente:

4. Impatto sulle prestazioni:

Vantaggi architetturali:

I TLB aggiuntivi permettono di alleggerire il carico sul TLB principale, velocizandone le operazioni.

Fonte: Paginazione.md

Conclusioni:

Il TLB rappresenta un componente assolutamente critico per le prestazioni dei sistemi moderni perché:

  1. Elimina l’overhead del table-walk nella maggior parte dei casi
  2. Sfrutta la località degli accessi alla memoria dei programmi
  3. Permette parallelismo attraverso architetture multi-TLB
  4. Mantiene coerenza con il sistema di paginazione tramite invalidazione controllata
  5. Scala efficacemente con dimensioni di pagina diverse

Senza il TLB, la memoria virtuale sarebbe praticamente inutilizzabile nei sistemi ad alte prestazioni, rendendo questo componente un esempio perfetto di come l’hardware specialized possa risolvere bottleneck architetturali fondamentali.

Approfondimenti:

Domanda 6.10

Domanda: Come viene gestito il bit D (dirty) nel TLB? Qual è il problema e la soluzione?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.11

Domanda: Cosa sono le regioni e sottoregioni nella paginazione? Come si calcola la dimensione di una regione di livello i?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.12

Domanda: Descrivi le funzioni map() e unmap() per la gestione delle traduzioni. Come funzionano i parametri template e le espressioni lambda?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.13

Domanda: Come funziona l’iteratore tab_iter? Qual è la differenza tra visite anticipate e posticipate?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.14

Domanda: Spiega i bit di controllo nelle entrate delle tabelle: P, R/W, U/S, PCD, PWT, A, D.

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.15

Domanda: Come vengono gestite le pagine di grandi dimensioni (2MB, 1GB)? Cosa cambia nel TLB?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.16

Domanda: Qual è la differenza tra it.next() e it.down() nell’iteratore tab_iter?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.17

Domanda: Come è organizzata la memoria virtuale di un processo nel sistema studiato? Descriva la divisione tra sezioni sistema e utente, condivise e private.

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.18

Domanda: Descriva il ciclo nelle tabelle di livello 4 e 3 della paginazione.

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.19

Domanda: Cosa è il descrittore di frame e come viene utilizzato nella gestione della memoria?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 6.20

Domanda: Come vengono gestite le istruzioni LOAD e STORE nel contesto della memoria virtuale?

Risposta: [La risposta verrà aggiunta quando richiesta]

7. Sistemi Multiprocesso e Processi

Domanda 7.1 (answered)

Domanda: Cosa si intende per processo in un sistema multiprocesso? Quali sono le differenze tra programma e processo?

Risposta: In un sistema multiprocesso, il concetto di processo rappresenta un’astrazione fondamentale che distingue nettamente l’entità statica del programma dalla sua esecuzione dinamica nel sistema.

Definizione di Processo:

Un processo è un programma in esecuzione su dei dati di ingresso

Fonte: Sistemi Multiprocesso e Processi.md

Questa esecuzione la possiamo modellare come la sequenza degli stati attraverso il cui il sistema processore+memoria passa eseguendo il programma.

Fonte: Sistemi Multiprocesso e Processi.md

Differenze fondamentali tra Programma e Processo:

1. Natura statica vs dinamica:

2. Molteplicità delle relazioni:

L’importante è capire che programma e processo sono due cose completamente distinte, infatti:

Fonte: Sistemi Multiprocesso e Processi.md

Esempi pratici:

3. Influenza dell’ambiente:

In generale non è esclusivamente il programma a decidere attraverso quali stati il processo dovrà passare, ma hanno influenze anche i vari segnali di input

Fonte: Sistemi Multiprocesso e Processi.md

4. Ripetizione e cicli:

Il programma potrebbe contenere dei cicli, che scrivono le cose da ripetere una sola volta, mentre nel processo vediamo le azioni ripetute tante volte.

Fonte: Sistemi Multiprocesso e Processi.md

Caratteristiche distintive del processo:

Contesto di esecuzione:

Il contesto di un processo comprenderà quindi:

Fonte: Sistemi Multiprocesso e Processi.md

Significato contestuale:

In un sistema multiprocesso infatti, il significato di una istruzione dipende dal processo che la sta eseguendo. Se un processo P1 esegue una istruzione MOV %rax, 1000 si sta riferendo al “suo” registro %rax e al “suo” indirizzo 1000. Mentre se la esegue un processo P2 parlerà di un diverso %rax e di un diverso contenuto dell’indirizzo 1000.

Fonte: Sistemi Multiprocesso e Processi.md

Stati di esecuzione del processo: Nel nostro sistema, ogni processo passa attraverso diversi stati durante la sua vita:

  1. Attivazione: Creazione delle strutture dati necessarie
  2. Pronto: Il processo è in attesa di essere selezionato per l’esecuzione
  3. Esecuzione: Il processo ha il controllo della CPU
  4. Bloccato: Il processo attende un evento (I/O, semaforo, ecc.)
  5. Terminazione: Il processo ha completato la sua esecuzione

Implementazione nel sistema: Dal file Sistemi Multiprocesso e Processi.md:

struct des_proc {
    natw id;                    // identificatore numerico del processo
    natw livello;              // livello di privilegio (LIV_UTENTE o LIV_SISTEMA)
    natl precedenza;           // precedenza nelle code dei processi
    vaddr punt_nucleo;         // indirizzo della base della pila sistema
    natq contesto[N_REG];      // copia dei registri generali del processore
    paddr cr3;                 // radice del TRIE del processo
    des_proc* puntatore;       // prossimo processo in coda
    void (*corpo)(natq);       // funzione da eseguire
    natq parametro;            // parametro della funzione
};

Gestione del cambio di contesto:

Per cambiare il contesto quando passiamo da un processo all’altro (ovvero quando eseguiamo swap-out e swap-in della memoria) utilizziamo tecniche sofware: Ogni volta che si effettua un cambio di processo, andiamo a salvare in una struttura dati i valori dei registri e della memoria del processo terminato. Successivamente copiamo i valori precedentemente salvati nella struttura dati associata al nuovo processo, rendendolo il processo corrente

Fonte: Sistemi Multiprocesso e Processi.md

Controllo dell’esecuzione:

Il registro RIP del processore si trova sempre in uno e uno solo dei processi. RIP non può attraversare due processi diversi, se non tramite il cambio di processo effettuato dal kernel stesso.

Fonte: Sistemi Multiprocesso e Processi.md

Ruolo del kernel:

Il kernel è quindi un software che sta sempre nello spazio di memoria di sistema (M1) e può riacquisire occasionalmente il controllo del flusso. Il kernel gira infatti a livello sistema e può recuperare il controllo del flusso solamente tramite i gate della IDT (interruzioni esterne, eccezioni, chiamate int)

Fonte: Sistemi Multiprocesso e Processi.md

Riepilogo delle differenze chiave:

Aspetto Programma Processo
Natura Statico, su disco Dinamico, in esecuzione
Contesto Nessuno Registri, memoria, stato
Ciclo di vita Permanente Nascita → esecuzione → morte
Interazione Nessuna Input/output, segnali
Molteplicità Uno → molti processi Uno → molti programmi
Controllo Passivo Attivo, controllato dal kernel

In sintesi, mentre un programma è semplicemente una sequenza di istruzioni memorizzate, un processo rappresenta l’esecuzione attiva di quel programma con il proprio contesto, stato e ciclo di vita, gestito dinamicamente dal sistema operativo.

Domanda 7.2 (answered)

Domanda: Cosa comprende il contesto di un processo? Come viene gestito durante i cambi di processo?

Risposta: Il contesto di un processo rappresenta tutte le informazioni necessarie per permettere al sistema di sospendere e riprendere l’esecuzione di quel processo specifico in modo trasparente. La gestione del contesto è fondamentale per il funzionamento di un sistema multiprogrammato.

Definizione del contesto di un processo:

Dal file Sistemi Multiprocesso e Processi.md:

Il contesto di un processo comprenderà quindi:

Componenti del contesto:

1. Stato dei registri del processore:

Tutti i registri generali del processore devono essere preservati:

Dal file Sistemi Multiprocesso e Processi.md:

struct des_proc {
    natw id;                    // identificatore numerico del processo
    natw livello;              // livello di privilegio (LIV_UTENTE o LIV_SISTEMA)
    natl precedenza;           // precedenza nelle code dei processi
    vaddr punt_nucleo;         // indirizzo della base della pila sistema
    natq contesto[N_REG];      // copia dei registri generali del processore
    paddr cr3;                 // radice del TRIE del processo
    des_proc* puntatore;       // prossimo processo in coda
    void (*corpo)(natq);       // funzione da eseguire
    natq parametro;            // parametro della funzione
};

2. Informazioni salvate automaticamente dall’hardware:

Quando si accede a un gate della IDT, il processore salva automaticamente 5 long word:

Quando si accede ad un gate della IDT (tramite interruzione, eccezione o int), sappiamo che vengono già salvate delle informazioni (5 long word):

Fonte: Sistemi Multiprocesso e Processi.md

3. Stato della memoria:

Meccanismo di gestione del contesto:

Principio fondamentale:

L’unico modo per transizionare da un processo ad un altro è tramite un gate della IDT.

Fonte: Sistemi Multiprocesso e Processi.md

Sequenza completa del cambio di contesto:

Dal file Sistemi Multiprocesso e Processi.md:

routine_gate:
    CALL salva_stato        ; Macro che salva il contenuto di tutti i registri in pila
    /*
    * corpo routine - qui può cambiare la variabile esecuzione
    */
    CALL carica_stato       ; Macro che carica il contenuto di tutti i registri dalla pila
    IRETQ

Funzioni di gestione del contesto:

1. salva_stato:

2. carica_stato:

Variabile esecuzione:

Per capire a quale processo ci stiamo riferendo quando invochiamo salva_stato e carica_stato utilizziamo come già detto una variabile globale esecuzione. esecuzione è implementata come un puntatore a descrittore di processo des_proc*

Fonte: Sistemi Multiprocesso e Processi.md

Gestione delle pile:

Meccanismo delle pile separate:

Quando entriamo nel gate da un processo P1 salviamo, tra le varie informazioni, l’indirizzo della pila utilizzata dal processo, nella sezione rsp della pila di sistema di P1. Facciamo ciò perché il registro rsp del processo in questo istante punta proprio alla pila di sistema di P1.

Fonte: Sistemi Multiprocesso e Processi.md

Ripristino del contesto:

Ciò significa che, carica_stato ripristinerà la pila di sistema del processo P2, e la successiva IRETQ ripristinerà proprio le istruzioni relative a quel processo, reinserendo il valore della pila di stack di P2.

Fonte: Sistemi Multiprocesso e Processi.md

Punto chiave:

Tutto il necessario per cambiare processo è quindi cambiare la variabile esecuzione all’interno del corpo della routine.

Fonte: Sistemi Multiprocesso e Processi.md

Atomicità delle operazioni:

Prevenzione dell’interferenza:

Dal file Realizzazione Primitive.md:

Per risolvere il problema delle interferenze è sufficiente rendere atomiche le primitive di sistema. L’atomicità implica che tutta l’operazione deve essere eseguita interamente oppure per niente, senza possibilità di essere interrotta.

Gestione della memoria del processo:

Tecnica software:

Per cambiare il contesto quando passiamo da un processo all’altro (ovvero quando eseguiamo swap-out e swap-in della memoria) utilizziamo tecniche sofware: Ogni volta che si effettua un cambio di processo, andiamo a salvare in una struttura dati i valori dei registri e della memoria del processo terminato. Successivamente copiamo i valori precedentemente salvati nella struttura dati associata al nuovo processo, rendendolo il processo corrente

Fonte: Sistemi Multiprocesso e Processi.md

Significato contestuale:

In un sistema multiprocesso infatti, il significato di una istruzione dipende dal processo che la sta eseguendo. Se un processo P1 esegue una istruzione MOV %rax, 1000 si sta riferendo al “suo” registro %rax e al “suo” indirizzo 1000. Mentre se la esegue un processo P2 parlerà di un diverso %rax e di un diverso contenuto dell’indirizzo 1000.

Fonte: Sistemi Multiprocesso e Processi.md

Esempio pratico di cambio contesto:

Scenario: Il processo P1 viene sospeso e il processo P2 viene messo in esecuzione:

  1. Evento scatenante: Interruzione, eccezione, o chiamata INT
  2. Salvataggio automatico: Hardware salva le 5 long word nella pila sistema di P1
  3. salva_stato: Salva tutti i registri di P1 in P1->contesto[N_REG]
  4. Corpo routine: Modifica esecuzione da P1 a P2
  5. carica_stato: Ripristina tutti i registri da P2->contesto[N_REG]
  6. IRETQ: Ripristina le 5 long word nella pila di P2 e gli trasferisce il controllo

Vantaggi di questo approccio:

  1. Trasparenza: Il processo non si accorge di essere stato sospeso
  2. Completezza: Tutto lo stato necessario viene preservato
  3. Efficienza: Cambio di contesto rapido tramite operazioni di copia
  4. Sicurezza: Ogni processo ha il proprio spazio privato
  5. Atomicità: Le operazioni sono protette dalle interruzioni

Collegamento con altri argomenti:

Conclusione:

Il contesto di un processo comprende tutti i registri, la memoria e le informazioni di stato necessarie per la sua esecuzione. La gestione del contesto avviene attraverso un meccanismo atomico e sicuro che utilizza i gate della IDT, le funzioni salva_stato e carica_stato, e la variabile globale esecuzione. Questo sistema garantisce che ogni processo possa essere sospeso e ripreso in modo completamente trasparente, permettendo l’implementazione efficace della multiprogrammazione.

Domanda 7.3

Domanda: Qual è il ruolo del kernel in un sistema multiprocesso? Come riacquisisce il controllo?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 7.4

Domanda: Descrivi gli stati di esecuzione di un processo: pronto, esecuzione, bloccato, terminazione.

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 7.5

Domanda: Come funziona la schedulazione a priorità fissa? Quando è necessaria la schedulazione?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 7.6

Domanda: Cosa significa preemption? Quando è necessaria nel nostro sistema?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 7.7

Domanda: Come avviene la transizione tra processi tramite i gate della IDT?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 7.8

Domanda: Spiega la struttura del descrittore di processo (des_proc). Cosa contiene ogni campo?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 7.9

Domanda: Cosa contiene la pila sistema di un processo? Come vengono impostati RIP, CS, RFLAGS?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 7.10

Domanda: Qual è il ruolo del processo dummy? Perché è necessario?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 7.11

Domanda: Descrivi l’organizzazione dei moduli sistema, io e utente. Come interagiscono tra loro?

Risposta: [La risposta verrà aggiunta quando richiesta]

8. Realizzazione delle Primitive

Domanda 8.1 (answered)

Domanda: Cos’è il contesto di un processo e come viene gestito il cambio di contesto in un sistema multiprogrammato?

Risposta: Definizione del contesto di un processo:

Il contesto di un processo rappresenta tutto lo stato necessario per eseguire quel processo specifico. Nel nostro sistema comprende:

Il contesto di un processo comprenderà quindi:

Fonte: Sistemi Multiprocesso e Processi.md

Struttura dati del descrittore di processo:

Nel sistema, ogni processo ha un descrittore des_proc che contiene:

struct des_proc {
    natw id;                    // identificatore numerico del processo
    natw livello;              // livello di privilegio (LIV_UTENTE o LIV_SISTEMA)
    natl precedenza;           // precedenza nelle code dei processi
    vaddr punt_nucleo;         // indirizzo della base della pila sistema
    natq contesto[N_REG];      // copia dei registri generali del processore
    paddr cr3;                 // radice del TRIE del processo
    des_proc* puntatore;       // prossimo processo in coda
    void (*corpo)(natq);       // funzione da eseguire
    natq parametro;            // parametro della funzione
};

Fonte: Sistemi Multiprocesso e Processi.md

Meccanismo del cambio di contesto:

1. Principio fondamentale:

L’unico modo per transizionare da un processo ad un altro è tramite un gate della IDT.

Fonte: Sistemi Multiprocesso e Processi.md

2. Implementazione del cambio contesto:

Il cambio contesto è realizzato tramite le funzioni salva_stato e carica_stato:

routine_gate:
    CALL salva_stato        ; Macro che salva il contenuto di tutti i registri in pila
    /*
    * corpo routine - qui può cambiare la variabile esecuzione
    */
    CALL carica_stato       ; Macro che carica il contenuto di tutti i registri dalla pila
    IRETQ

Tutto il necessario per cambiare processo è quindi cambiare la variabile esecuzione all’interno del corpo della routine.

Fonte: Sistemi Multiprocesso e Processi.md

3. Gestione della variabile esecuzione:

Per capire a quale processo ci stiamo riferendo quando invochiamo salva_stato e carica_stato utilizziamo come già detto una variabile globale esecuzione. esecuzione è implementata come un puntatore a descrittore di processo des_proc*

Fonte: Sistemi Multiprocesso e Processi.md

4. Atomicità delle primitive:

Per garantire la correttezza del sistema, le primitive devono essere atomiche:

Per risolvere il problema delle interferenze è sufficiente rendere atomiche le primitive di sistema. L’atomicità implica che tutta l’operazione deve essere eseguita interamente oppure per niente, senza possibilità di essere interrotta.

Fonte: Realizzazione Primitive.md

Riepilogo del processo completo:

  1. Un gate della IDT viene attraversato (interruzione, eccezione, o int)
  2. Il processore salva automaticamente 5 long word in pila (RIP, CS, RFLAGS, RSP, SS)
  3. salva_stato salva tutti i registri nell’array contesto del processo corrente
  4. Il corpo della routine può modificare la variabile esecuzione
  5. carica_stato ripristina i registri dall’array contesto del nuovo processo
  6. IRETQ ripristina le 5 long word e trasferisce il controllo al nuovo processo

Questo meccanismo garantisce che ogni processo mantenga il proprio contesto privato e che i cambi di contesto avvengano in modo atomico e sicuro.

Domanda 8.2

Domanda: Come avviene la creazione dei processi nel sistema? Quali sono gli stati di esecuzione dei processi? A che punto del codice un processo si può dire effettivamente in esecuzione?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 8.3

Domanda: Come funziona l’I/O nel sistema multiprogrammato? Quali sono gli accorgimenti da fare per mutex e sync?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 8.4

Domanda: Descriva l’avvio del sistema: quali strutture vengono create e come vengono inizializzate?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 8.5

Domanda: Come avviene il cambio di processo? Perché punt_nucleo punta alla base?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 8.6

Domanda: Come si passa il parametro alla activate_p()? Chi è che usa punt_nucleo?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 8.7

Domanda: Perché usiamo una pila sistema diversa per ogni processo?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 8.8

Domanda: Come è organizzata la memoria virtuale di un processo nel sistema studiato?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 8.9

Domanda: Spieghi il problema dell’interferenza tra flussi di esecuzione. Faccia un esempio concreto di cosa potrebbe accadere durante l’inserimento di un processo nella coda “pronti”, e esponga come viene risolto il problema degli stati inconsistenti nelle strutture dati del sistema

Risposta: [La risposta verrà aggiunta quando richiesta]

9. Semafori

Domanda 9.1 (answered)

Domanda: Definisca i due problemi fondamentali della programmazione concorrente: mutua esclusione e sincronizzazione. Faccia esempi pratici per entrambi.

Risposta: I due problemi fondamentali della programmazione concorrente nascono quando più processi o thread devono lavorare insieme condividendo risorse. Nel nostro sistema, dove i processi utente condividono memoria comune, questi problemi diventano critici.

Contesto:

Per quanto riguarda la condivisione della memoria, nel nostro sistema i processi utente:

Fonte: Semafori.md

L’utente che scrive un’applicazione strutturata su più processi concorrenti deve affrontare dei problemi molto simili a quelli già affrontati a livello sistema. In particolare, anche l’utente deve affrontare il problema dell’interferenza

Fonte: Semafori.md

1. MUTUA ESCLUSIONE

Definizione:

Mutua esclusione: l’ordine nel quale eseguiamo le varie attività non è rilevante.

Fonte: Semafori.md

Esempio pratico fornito dal corso:

Un esempio pratico è la gestione del bagno durante un’esame. Non possono infatti esserci più studenti nello stesso momento in bagno, ed è necessario che uno torni poiché possa andare il prossimo. Tuttavia non è importante che uno studente vada prima di un altro.

Fonte: Semafori.md

Esempio informatico: Supponiamo di avere più processi che devono accedere a una struttura dati condivisa (es. un contatore globale):

// PROBLEMA: senza mutua esclusione
int contatore_globale = 0;

void incrementa() {
    int temp = contatore_globale;    // Legge valore corrente
    temp = temp + 1;                // Incrementa localmente
    contatore_globale = temp;       // Scrive il nuovo valore
}

Se due processi eseguono incrementa() contemporaneamente, potrebbero leggere lo stesso valore, incrementarlo entrambi, e scrivere lo stesso risultato, perdendo un incremento.

Soluzione con semafori:

Per risolvere questo problema è sufficente avere un semaforo che inizialmente contiene un gettone e imporre la regola che: “Solo chi ha il gettone può compiere una delle azioni. Al termine dell’azione è obbligatorio reinserire il gettone”

Fonte: Semafori.md

Dal file Semafori.md:

natl mutex = sem_ini(1);

void incrementa_sicuro() {
    sem_wait(mutex);        // Prende il gettone (entra in sezione critica)
    int temp = contatore_globale;
    temp = temp + 1;
    contatore_globale = temp;
    sem_signal(mutex);      // Rilascia il gettone (esce da sezione critica)
}

2. SINCRONIZZAZIONE

Definizione:

Sincronizzazione: alcune attività devono comunque essere eseguite prima di altre.

Fonte: Semafori.md

Esempio pratico fornito dal corso:

Un caso comune è quello in cui un processo produce dei dati e li scrive in un buffer intermedio, da cui in altro processo li preleva per svolgere ulteriori elaborazioni. In questo caso, finché il primo processo non ha prodotto i dati, il secondo non deve andare in esecuzione leggendoli. Allo stesso tempo chi scrive deve assicurarsi che l’altro ha letto correttamente tutti i dati, poiché li andrebbe a sovrascrivere.

Fonte: Semafori.md

Esempio dettagliato: Supponiamo due processi:

Problema: Il consumatore non deve leggere prima che il produttore abbia scritto, e il produttore non deve sovrascrivere dati non ancora letti.

Soluzione con due semafori:

È sufficiente in questo caso utilizzare due semafori:

Fonte: Semafori.md

Dal file Semafori.md:

natl mutex = sem_ini(1);    // Mutua esclusione per accesso al buffer
natl sync = sem_ini(0);     // Sincronizzazione: inizia vuoto

void produttore() {
    sem_wait(mutex);        // Accesso esclusivo al buffer
    // ... scrivi dati nel buffer ...
    sem_signal(sync);       // Segnala che i dati sono pronti
    sem_signal(mutex);      // Rilascia l'accesso al buffer
}

void consumatore() {
    sem_wait(sync);         // Aspetta che i dati siano pronti
    sem_wait(mutex);        // Accesso esclusivo al buffer
    // ... leggi dati dal buffer ...
    sem_signal(mutex);      // Rilascia l'accesso al buffer
}

Esempio avanzato - Handshake:

Nei casi di sincronizzazione, si può arrivare a sviluppare semafori che hanno funzionamento molto simile a quello degli handshake.

Fonte: Semafori.md

Dal file Semafori.md:

natl S1 = sem_ini(1);   // Permesso di scrittura
natl S2 = sem_ini(0);   // Segnalazione lettura completata

void scrittura() {
    sem_wait(S1);       // Aspetta il permesso di scrivere
    // corpo: scrivi nel buffer
    sem_signal(S2);     // Segnala che la scrittura è completata
}

void lettura() {
    sem_wait(S2);       // Aspetta che ci sia qualcosa da leggere
    // corpo: leggi dal buffer
    sem_signal(S1);     // Segnala che la lettura è completata
}

Differenze chiave:

Implementazione nel sistema: I semafori nel nostro sistema sono implementati tramite:

Questi meccanismi sono fondamentali per costruire applicazioni concorrenti corrette e efficienti, risolvendo i problemi di interferenza che altrimenti comprometterebbero la correttezza dei programmi.

Domanda 9.2 (answered)

Domanda: Come funzionano i semafori di Dijkstra? Spieghi le operazioni di inserimento e prelievo dei gettoni e il comportamento in caso di semaforo vuoto.

Risposta: I semafori di Dijkstra sono strumenti fondamentali per la sincronizzazione e la mutua esclusione nella programmazione concorrente, implementando un meccanismo elegante basato su “scatole” contenenti “gettoni”.

Origine e concetto base:

Questo nome fu dato da Dijkstra in relazione al fatto che nella prima formulazione ogni semaforo poteva assumere solo due stati:

Fonte: Semafori.md

Definizione concettuale:

Per risolvere i problemi di mutua esclusione e sincronizzazione, si suppone di avere delle scatore, chiamate semafori che possono contenere degli oggetti, chiamati gettoni, tutti uguali.

Fonte: Semafori.md

1. Le due operazioni fondamentali:

Nei semafori possono essere eseguite solo due operazioni con i gettoni: Inserimento e Prelievo.

Fonte: Semafori.md

A) Operazione di Inserimento (sem_signal):

Per quanto riguarda l’inserimento, non è necessario che il processo che insersce il gettone lo abbia precedentemente prelevato da qualche parte, può infatti crearlo sul momento.

B) Operazione di Prelievo (sem_wait):

Nel caso invece del prelievo del gettone, se questo non è presente, il processo deve aspettare che qualcun altro ne inserisca uno, entrando in uno stato di attesa dove non può fare nient’altro

2. Interfaccia del sistema:

Dal file Semafori.md:

/**
 * Crea un nuovo semaforo con n gettoni
 * @param n : numero gettoni
 * @return identificatore (0xFFFFFFFF se non è stato possibile crearlo)
 */
sem = sem_ini(n);     

/**
 * Prende un gettone. Blocca il processo se il semaforo è vuoto
 * @param sem : numero del semaforo
 */
sem_wait(sem);

/**
 * Inserisce un gettone, risvegliando uno dei processi bloccati in attesa
 * @param sem: numero del semaforo 
 */
sem_signal(sem);

3. Struttura dati interna:

Implementazione nel sistema:

Per realizzare i semafori prevediamo la seguente struttura dati definita nel codice sistema:

struct des_sem {
    /// se >= 0, numero di gettoni contenuti;
    /// se < 0, il valore assoluto è il numero di processi in coda
    int counter;
    /// coda di processi bloccati sul semaforo
    des_proc* pointer;
};

Fonte: Semafori.md

Significato dei campi:

4. Operazione sem_wait() - Prelievo gettone:

Implementazione dettagliata:

Dal file Semafori.md:

extern "C" void c_sem_wait(natl sem){
    // una primitiva non deve mai fidarsi dei parametri
    if (!sem_valido(sem)) {
        flog(LOG_WARN, "sem_wait: semaforo errato: %u", sem);
        c_abort_p();
        return;
    }

    des_sem* s = &array_dess[sem];
    s->counter--;

    if (s->counter < 0) {
        inserimento_lista(s->pointer, esecuzione);
        schedulatore();
    }
}

Comportamento dettagliato:

  1. Validazione: Controlla che l’identificatore del semaforo sia valido
  2. Decremento: Riduce sempre il contatore di 1
  3. Controllo disponibilità:
    • Se counter ≥ 0: Il gettone era disponibile, il processo continua
    • Se counter < 0: Semaforo vuoto → il processo viene bloccato

Comportamento in caso di semaforo vuoto:

Nel caso di semaforo senza gettoni, il processo attualmente in esecuzione viene inserito nella coda del semaforo e ne viene scelto un altro invocando la funzione schedulatore(). Questa non fa altro che estrarre dalla coda pronti il processo a più alta priorità e lo fa puntare dalla variabile esecuzione. In questo modo, la routine carica_stato (che verrà eseguita subito dopo) farà saltare al nuovo processo, di fatto bloccando il precedente.

5. Operazione sem_signal() - Inserimento gettone:

Implementazione dettagliata:

extern "C" void c_sem_signal(natl sem)
{
    // una primitiva non deve mai fidarsi dei parametri
    if (!sem_valido(sem)) {
        flog(LOG_WARN, "sem_signal: semaforo errato: %u", sem);
        c_abort_p();
        return;
    }

    des_sem* s = &array_dess[sem];
    s->counter++;

    if (s->counter <= 0) {
        des_proc* lavoro = rimozione_lista(s->pointer);
        inspronti();    // preemption
        inserimento_lista(pronti, lavoro);
        schedulatore(); // preemption
    }
}

Comportamento dettagliato:

  1. Validazione: Controlla che l’identificatore del semaforo sia valido
  2. Incremento: Aumenta sempre il contatore di 1
  3. Controllo processi in attesa:
    • Se counter > 0: Nessun processo in attesa, il gettone rimane disponibile
    • Se counter ≤ 0: Ci sono processi in attesa → risveglia il processo a priorità più alta

Gestione del risveglio:

Se ci sono processi in coda sul semaforo, la primitiva estrae quello a priorità più alta attraverso la funzione rimozione_lista(). A questo punto la primitiva deve scegliere quale processo deve proseguire, tra quello in esecuzione e quello appena estratto. La cosa più semplice è di inserire entrambi i processi in coda pronti e lasciar scegliere alla funzione schedulatore(), applicando la preemption.

6. Esempio pratico - Mutua Esclusione:

Configurazione:

natl mutex = sem_ini(1);    // Inizializza con UN gettone

void sezione_critica() {
    sem_wait(mutex);        // Prende il gettone (blocca altri)
    // ... operazioni critiche ...
    sem_signal(mutex);      // Rilascia il gettone
}

Scenario operativo:

Se una persona vuole compiere un’azione deve prendere il gettone, svuotando la scatola. Se una seconda persona volesse compiere la stessa azione troverà il semaforo vuoto, e si troverà costretta attendere che la prima termini la sua.

Fonte: Semafori.md

7. Preemption e priorità:

Effetto sulla schedulazione:

Possiamo notare come in casi come questo può avvenire preemption. Quando un processo riesce finalmente a recuperare il gettone, torna nella pila pronti, ed è quasi certo che abbia una priorità più elevata del processo attualmente in esecuzione, forzandone lo scambio.

Fonte: Semafori.md

8. Gestione errori e validazione:

Controlli di sicurezza:

Sia la sem_wait() che la sem_signal(), prima di usare sem, controllano che questo sia un valido identificatore di semaforo, ovvero che sia stato precedentemente restituito da una sem_ini() per il livello corretto, e terminare forzatamente il processo in caso contrario.

Fonte: Semafori.md

Approfondimenti:

Riepilogo funzionamento:

  1. sem_ini(n): Crea semaforo con n gettoni iniziali
  2. sem_wait(): Decrementa sempre; se risultato negativo blocca il processo
  3. sem_signal(): Incrementa sempre; se c’erano processi in attesa ne risveglia uno
  4. Contatore: Positivo = gettoni disponibili, negativo = processi in attesa
  5. Coda processi: Ordinata per priorità, gestita automaticamente dal sistema

I semafori di Dijkstra forniscono quindi un meccanismo robusto e elegante per coordinare l’accesso alle risorse condivise in ambienti concorrenti.

Domanda 9.3

Domanda: Descriva cosa accade se il processo si sospende su un semaforo? Come viene gestita questa situazione?

Risposta: [La risposta verrà aggiunta quando richiesta]

10. Delay e Gestione del Tempo

Domanda 10.1 (answered)

Domanda: Come viene implementata la primitiva delay(n) nel sistema? Perché non si decrementa semplicemente un contatore per ogni processo sospeso?

Risposta: La primitiva delay(n) è implementata attraverso un sistema sofisticato di gestione dei processi sospesi che utilizza un timer hardware e una lista ordinata per ottimizzare le prestazioni. Il sistema evita di decrementare singoli contatori per motivi di efficienza computazionale.

Implementazione del sistema timer:

Per realizzare questa funzionalità, il metodo più semplice è quello di impostare un timer affinché venga inviata una richiesta di interruzione con periodo fisso. Questa è la soluzione che attuiamo nel nostro sistema, utilizzando il timer 0 del PC AT, e programmandolo in modo che invii una richiesta ogni 50ms.

Fonte: Delay e new.md

Funzionamento della primitiva delay(n):

Forniamo inoltre una primitiva void delay(natl n) tramite la quale un processo può chiedere di essere sospeso per n cicli del timer. La primitiva inserisce il processo in una coda di processi sospesi, salvando il valore di n.

Fonte: Delay e new.md

Problema del decremento di contatori singoli:

Se k fosse molto grande, andare a modificare tutti i singoli ni risulterebbe in un operazione molto costosa, poiché richiederebbe che il driver debba decrementare tutti i k contatori ad ogni interruzione del timer.

Fonte: Delay e new.md

Soluzione ottimizzata - Lista ordinata con valori relativi:

Dal file Delay e new.md:

// Operativamente quello che facciamo è quindi diverso:
// - Manteniamo i processi in attesa in una lista ordinata per cicli di attesa crescenti
// - Per ogni processo non salviamo il numero di cicli totali che deve attendere,
//   ma quanti cicli in più rispetto al precedente

struct richiesta {
    natl d_attesa;      // tempo di attesa aggiuntivo rispetto alla richiesta precedente
    richiesta* p_rich;  // puntatore alla richiesta successiva
    des_proc* pp;       // descrittore del processo che ha effettuato la richiesta
};

In altre parole, l’elemento in cima alla lista $r_1$ memorizza $n_1$, gli elementi $r_i$ con $(1 < i \le k)$ memorizzeranno: $n_i - n_{i-1}$.

Fonte: Delay e new.md

- Vantaggi del sistema di valori relativi

In questo modo il driver deve occuparsi di decrementare solo l’elemento in testa alla lista. Quando questo elemento avrà il contatore a $0$, allora sposteremo i primi $k$ elementi con contatore nullo nella lista pronti, reinserendovi anche il processo in esecuzione, per poi chiamare lo schedulatore().

Fonte: Delay e new.md

Implementazione del driver del timer:

Dal file Delay e new.md:

extern "C" void c_driver_td(void) {
    inspronti();

    if (sospesi != nullptr) {
        sospesi->d_attesa--;    // Decrementa solo il primo elemento
    }

    while (sospesi != nullptr && sospesi->d_attesa == 0) {
        inserimento_lista(pronti, sospesi->pp);
        richiesta* p = sospesi;
        sospesi = sospesi->p_rich;
        delete p;
    }

    schedulatore();
}

Approfondimenti:

Domanda 10.2

Domanda: Spieghi l’algoritmo di gestione della lista ordinata dei processi sospesi. Come vengono calcolati i valori relativi invece che assoluti?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 10.3

Domanda: Come facciamo nel nostro nucleo a creare un modo per far sì che i processi partano e dopo un tot di tempo vadano in fondo alla coda pronti?

Risposta: [La risposta verrà aggiunta quando richiesta]

11. Bus PCI

Domanda 11.1 (answered)

Domanda: Quali problemi risolve lo standard PCI rispetto al bus ISA? Come viene evitato il problema degli indirizzi sovrapposti?

Risposta: Lo standard PCI (Peripheral Component Interconnect) risolve diversi problemi critici del bus ISA, introducendo meccanismi innovativi per garantire compatibilità, espandibilità e gestione automatica delle risorse hardware.

Problemi del bus ISA:

Dal momento che il PC AT era costruito con parti standard, il suo bus venne chiamato ISA (Industry Standard Architecture). Questo bus era però molto limitato e descriveva tutti i limiti del PC AT.

Fonte: PCI.md

Problema principale - Conflitti di indirizzi:

La maggior parte dei computer dell’epoca (come oggi) erano espandibili, ovvero potevano essere inserite delle schede di espansione indipendenti da IBM per aggiungere funzionalità al sistema. Tuttavia questa possibilità generò dei problemi, specialmente in un mercato dove non era presente il coordinamento tra i vari produttori di schede. Poteva infatti capitare che due schede diverse facessero riferimento agli stessi indirizzi di memoria, e che quindi quegli indirizzamenti fossero sovrapposti.

Fonte: PCI.md

Questo problema si propagava anche in come venivano scritti i driver, che non erano quindi più in grado di distinguere se la scheda desiderata era effettivamente inserita, se si trattava di una scheda diversa oppure se non ci fosse installato nulla.

Fonte: PCI.md

Innovazioni dello standard PCI:

1. Universalità e indipendenza dal processore:

Nel 1992 la Intel propose lo standard Peripheral Component Interconnect, all’epoca a 32bit, valido per qualsiasi tipo di processore, non solo Intel.

Fonte: PCI.md

2. Tre spazi di indirizzamento:

Lo standard definisce inoltre tre spazi di indirizzamento: spazio di memoria, spazio di I/O e spazio di configurazione. I primi due spazi sono completamente analoghi a quelli che già conosciamo e sono quelli che il software deve utilizzare per dialogare con le periferiche connesse al bus.

Fonte: PCI.md

- Soluzione al problema degli indirizzi sovrapposti:

Meccanismo dei comparatori programmabili:

Per garantire il vincolo che i registri delle periferiche non occupino indirizzi sovrapposti si introducono due regole:

  1. Le periferiche che rispettano lo standard non possono scegliere autonomamente gli indirizzi dei propri registri, ma devono contenere dei comparatori programmabili in modo che questi indirizzi siano impostati dal software della macchina.
  2. Il software può impostare questi comparatori all’avvio del sistema, tramite il nuovo spazio di configurazione.

Fonte: PCI.md

Spazio di configurazione:

Lo spazio di configurazione è fatto in modo da poter accedere a dei registri di configurazione che ogni periferica deve avere per rispettare lo standard in modo univoco e senza conflitti. Tramite questi registri il software di avvio (PCI BIOS) può scoprire quali periferiche sono connesse al bus. Non solo, capisce anche di quanti indirizzi hanno bisogno e programma di conseguenza i comparatori affinché non ci siano sovrapposizioni.

Fonte: PCI.md

- Processo di configurazione automatica

Dal file PCI.md:

// Registri BAR (Base Address Register) per ogni funzione:
// - Il software di inizializzazione scopre le dimensioni richieste
// - Assegna regioni non sovrapposte
// - Programma i comparatori delle periferiche
// - Abilita le funzioni tramite il registro Command

// Esempio di configurazione:
// 1. Lettura Vendor ID e Device ID per identificare la periferica
// 2. Lettura dei BAR per scoprire requisiti di spazio
// 3. Assegnazione indirizzi univoci
// 4. Attivazione tramite registro Command

Meccanismo di indirizzamento nel bus:

Fase di Indirizzamento: dopo che l’iniziatore specifica il tipo di operazione e l’indirizzo del primo byte da leggere/scrivere, tutti i dispositivi che hanno registri nello spazio confrontano queste informazioni con il contenuto dei loro comparatori. Al più uno troverà una corrispondenza, e quello diventerà l’obiettivo della transazione.

Fonte: PCI.md

Approfondimenti:

Vantaggi rispetto al bus ISA:

  1. Configurazione automatica vs configurazione manuale
  2. Assegnazione dinamica degli indirizzi vs indirizzi fissi
  3. Rilevamento automatico delle periferiche vs configurazione statica
  4. Eliminazione dei conflitti attraverso software vs gestione manuale

Domanda 11.2 (answered)

Domanda: Cosa sono i tre spazi di indirizzamento definiti dallo standard PCI e qual è il ruolo dello spazio di configurazione?

Risposta: Il bus PCI (Peripheral Component Interconnect) definisce tre spazi di indirizzamento distinti per gestire la comunicazione tra CPU e periferiche in modo organizzato e senza conflitti. Ogni spazio ha caratteristiche e scopi specifici.

- I tre spazi di indirizzamento PCI

Dal file PCI.md:

Lo standard definisce inoltre tre spazi di indirizzamento: spazio di memoria, spazio di I/O e spazio di configurazione.

I primi due spazi sono completamente analoghi a quelli che già conosciamo e sono quelli che il software deve utilizzare per dialogare con le periferiche connesse al bus.

1. Spazio di Memoria

Caratteristiche:

2. Spazio di I/O

Caratteristiche:

Dal file PCI.md:

La dimensione del blocco è $2^b$ dove $b$ è il numero di bit non scrivibili utilizzati per fornire al software di inizializzazione indicazioni sul tipo di blocco e sulla sua dimensione. In particolare il bit 0 serve a capire se il blocco è pensato per lo spazio di I/O (1) o di memoria (0).

3. Spazio di Configurazione

Caratteristiche:

- Ruolo specifico dello spazio di configurazione

Lo spazio di configurazione rappresenta l’innovazione principale del bus PCI per risolvere i conflitti di indirizzamento.

Funzioni principali:

1. Identificazione automatica delle periferiche

Dal file PCI.md:

Tramite questi registri il software di avvio (PCI BIOS) può scoprire quali periferiche sono connesse al bus. Non solo, capisce anche di quanti indirizzi hanno bisogno e programma di conseguenza i comparatori affinché non ci siano sovrapposizioni.

2. Assegnazione automatica degli indirizzi

Lo scopo principale della fase di configurazione dei dispositivi è quello di assegnare indirizzi univoci negli spazi di I/O e/o di memoria.

3. Controllo dei comparatori programmabili

Dal file PCI.md:

Le periferiche che rispettano lo standard non possono scegliere autonomamente gli indirizzi dei propri registri, ma devono contenere dei comparatori programmabili in modo che questi indirizzi siano impostati dal software della macchina.

Struttura dell’indirizzamento di configurazione:

Indirizzo di configurazione composto da:

Registri obbligatori dello spazio di configurazione:

Dal file PCI.md:

Tutte le funzioni devono avere i seguenti registri:

Meccanismo di accesso al PC:

Registri del ponte ospite-PCI:

Dal file PCI.md:

Una volta che CAP è stato impostato, il ponte ospite-PCI tradurrà le letture e le scritture in CDP in corrispondenti transizioni nello spazio di configurazione.

Registri BAR (Base Address Register):

Funzione dei BAR:

Dal file PCI.md:

Il software di inizializzazione sceglierà quindi la regione e ne scriverà il numero nei bit scrivibili del BAR, così che contenga l’indirizzo di partenza del blocco.

Processo di configurazione automatica:

  1. Scoperta: Il BIOS esplora lo spazio di configurazione
  2. Identificazione: Legge Vendor ID, Device ID e Class Code
  3. Dimensionamento: Analizza i BAR per scoprire i requisiti di spazio
  4. Assegnazione: Programma i comparatori con indirizzi univoci
  5. Attivazione: Abilita le funzioni tramite il registro Command

Vantaggi dello spazio di configurazione:

  1. Eliminazione dei conflitti di indirizzamento tra periferiche
  2. Configurazione automatica senza intervento manuale
  3. Identificazione univoca di ogni periferica e funzione
  4. Standardizzazione dell’interfaccia di configurazione
  5. Supporto per architetture complesse con più bus

Collegamento con altri argomenti:

Domanda 11.3 (answered)

Domanda: Come avvengono le trasmissioni all’interno di un architettura con il bus PCI?

Risposta: Le trasmissioni nel bus PCI seguono un protocollo strutturato a fasi che garantisce comunicazione affidabile e coordinata tra dispositivi attraverso un meccanismo di handshake e arbitraggio, permettendo trasferimenti efficienti tra iniziatori e obiettivi.

Concetto fondamentale di transazione:

Dal file PCI.md:

Le operazioni (lettura, scrittura, …) sul bus PCI sono dette transazioni. Le transazioni sono iniziate da un dispositivo iniziatore che cerca di operare su un altro dispositivo obiettivo, e seguono il clock.

Caratteristica chiave:

Lo standard permette a qualsiasi dispositivo di essere iniziatore o obiettivo in transazioni diverse. Questo meccanismo permette il meccanismo di accesso diretto alla memoria di cui parleremo in seguito.

Fonte: PCI.md

Struttura delle transazioni:

1. Fasi della transazione:

Dal file PCI.md:

Le transazioni si svolgono in più fasi:

2. Segnali di controllo principali:

Segnale Iniziatore Obiettivo Funzione
FRAME# Uscita Ingresso Delimita l’inizio e il termine di ogni transazione
DEVSEL# Ingresso Uscita Segnale che l’obiettivo riconosce uno dei propri indirizzi
C[3:0] Uscita Ingresso Codificano il tipo di operazione nell’indirizzamento
BE#[3:0] Uscita Ingresso Fungono da byte-enabler nelle fasi di trasferimento
AD[31:0] I/O I/O Indirizzo (fase addressing) / Dati (fasi trasferimento)
TRDY# Ingresso Uscita Target ready - Handshake nelle fasi di scambio dati
IRDY# Uscita Ingresso Initiator ready - Handshake nelle fasi di scambio dati
STOP# Ingresso Uscita Termina prematuramente una transazione
CLK Ingresso Ingresso Clock di sincronizzazione (33MHz o 64MHz)

Protocollo di trasmissione dettagliato:

1. Inizializzazione della transazione:

Dal file PCI.md:

Il collegamento segue il seguente protocollo:

2. Operazioni di lettura:

Meccanismo handshake per la lettura:

Dal file PCI.md:

Nelle operazioni di lettura:

Sequenza completa:

  1. Iniziatore specifica indirizzo e tipo operazione
  2. Obiettivo attiva DEVSEL# se riconosce l’indirizzo
  3. Obiettivo mette i dati su AD[31:0] e attiva TRDY#
  4. Iniziatore legge i dati e attiva IRDY#
  5. Entrambi TRDY# e IRDY# attivi → trasferimento completato

3. Operazioni di scrittura:

Meccanismo handshake per la scrittura:

Dal file PCI.md:

Nelle operazioni di scrittura invece avviene l’opposto:

Sequenza completa:

  1. Iniziatore specifica indirizzo e tipo operazione
  2. Obiettivo attiva DEVSEL# se riconosce l’indirizzo
  3. Iniziatore mette i dati su AD[31:0] e byte-enable su BE#[3:0], attiva IRDY#
  4. Obiettivo riceve i dati e attiva TRDY#
  5. Entrambi TRDY# e IRDY# attivi → trasferimento completato

Caratteristiche prestazionali:

1. Trasferimenti multi-fase:

Dal file PCI.md:

Ogni fase dati trasferisce al più 4Byte allineati naturalmente. Ciascuna fase si conclude quando sia IRDY# che TRDY# sono attivi sullo stesso fronte di salita del clock.

2. Ottimizzazione dei trasferimenti:

Il riutilizzo delle stesse linee per scopi diversi riduce i costi a scapito però della velocità di trasferimento. Fortunatamente, la possibilità di eseguire più fasi dati con una singola fase di indirizzamento ci fa recuperare un po’ di velocità. È infatti sufficiente che l’iniziatore mantenga FRAME# attivo quando lo è anche IRDY#.

Fonte: PCI.md

Gestione delle interruzioni:

Terminazione prematura:

L’obiettivo può inoltre attivare STOP# per terminare forzatamente la transazione.

Fonte: PCI.md

Arbitraggio nel Bus Mastering:

Coordinamento dispositivi multipli:

Dal file DMA.md:

Poiché diversi dispositivi possono agire da bus master dobbiamo prevederne un coordinamento, affinché non possano entrare in comunicazione tutti insieme. Introduciamo quindi un arbitro, un ulteriore dispositivo (spesso integrato nel ponte stesso) che gestisce tramite handshake tutte le richieste di trasferimento. Quando un bus master vuole iniziare una richiesta invia il segnale di REQ all’arbitro. Appena è il suo turno l’arbitro invia un segnale chiamato di grant GNT o segnale di acknowledge ACK.

Ottimizzazione temporale:

Per ottimizzare i tempi, l’arbitraggio può verificarsi mentre è ancora in corso una precedente transazione. Infatti il dispositivo che ottiene GNT, prima di iniziare la propria transazione, necessita comunque che sia FRAME# che IRDY# siano disattivati, ovvero che il bus sia libero. Perciò rimarrà in attesa finché la precedente operazione non sarà terminata.

Fonte: DMA.md

Architettura Bus Master:

Ruolo del ponte:

Dal file DMA.md:

Per essere precisi, in realtà i bus master inizializzano il trasferimento verso il ponte non direttamente verso la RAM. È infatti quest’ultimo che poi reindirizza i dati alla RAM. Le informazioni vengono quindi passate attraverso l’arbitro al ponte, che poi si occuperà di trasferirle al destinatario sul bus principale.

Bufferizzazione:

Nonostante il trasferimento avvenga quindi in asincrono, il ponte invia comunque un segnale di trasferimento completato al bus master che si occupa delle operazioni nel momento della ricezione in locale delle informazioni. Questo permette infatti di ottimizzare i tempi, facendo iniziare un nuovo ciclo di ricezione/scrittura dati, anche quando in realtà le informazioni sono ancora contenute solamente in locale al ponte. Questa tipo di gestione delle informazioni viene chiamata bufferizzazione.

Fonte: DMA.md

Temporizzazioni e sincronizzazione:

Clock di riferimento:

Vantaggi del protocollo PCI:

  1. Flessibilità: Qualsiasi dispositivo può essere iniziatore o obiettivo
  2. Efficienza: Trasferimenti burst con multiple fasi dati per singolo indirizzamento
  3. Affidabilità: Handshake garantisce trasferimenti corretti
  4. Scalabilità: Arbitraggio permette multiple richieste simultanee
  5. Ottimizzazione: Bufferizzazione e pipelining delle operazioni

Confronto con architetture precedenti:

Aspetto Bus ISA Bus PCI
Arbitraggio Fisso/manuale Dinamico via arbitro hardware
Configurazione Manuale (jumper) Automatica (spazio configurazione)
Iniziatori Solo CPU Qualsiasi dispositivo (Bus Master)
Handshake Limitato Completo (IRDY#/TRDY#)
Trasferimenti burst Non supportati Supportati con multiple fasi dati
Gestione conflitti Problematica Risolta via comparatori programmabili

Approfondimenti:

Il protocollo PCI rappresenta quindi un equilibrio ottimale tra semplicità implementativa, prestazioni e flessibilità, fornendo le basi per tutte le architetture di comunicazione moderne.

12. I/O e Driver

Domanda 12.1 (answered)

Domanda: Perché in un sistema protetto un processo non può dialogare direttamente con le periferiche? Come vengono gestite le primitive di I/O?

Risposta: In un sistema protetto, i processi utente non possono dialogare direttamente con le periferiche per garantire sicurezza, stabilità e controllo centralizzato dell’accesso alle risorse hardware.

Motivazioni della protezione:

1. Problema delle istruzioni privilegiate:

Aver implementato la Protezione implica adesso che se un processo vuole fare un’operazione di I/O, non può parlare direttamente con le periferiche (tastiera, video, …).

Fonte: IO.md

Andremo quindi a vietare le istruzioni di IN, OUT, CLI, STI per il contesto utente, permettendole solamente quando ci si trova nel contesto sistema.

Fonte: Protezione.md

2. Controllo dell’accesso alle risorse:

Le istruzioni IN e OUT sono fondamentali per comunicare con le periferiche, ma consentire l’accesso diretto comporterebbe rischi:

Nei processori Intel vi è un’associazione tra IN e OUT ai comandi CLI e STI. Se ponessimo il LIV_UTENTE, forniremmo l’accesso all’utente anche a queste istruzioni, cosa che abbiamo già visto non va fatta.

Fonte: IO.md

3. Problemi di sicurezza e interferenza:

Costringere l’utente 1 a scrivere il programma tramite routine invece di dialogare direttamente con il controllore Costringere l’utente 2 a non disattivare le interruzioni

Fonte: Protezione.md

Gestione delle primitive di I/O:

1. Architettura del sistema:

Il sistema è organizzato in tre moduli separati con livelli di privilegio differenti:

Il sistema che realizzeremo è organizzato in tre moduli:

I moduli sistema e utente vengono eseguiti con il processore a livello sistema, in un contesto privilegiato, mentre utente verrà eseguito al livello utente.

Fonte: Sistemi Multiprocesso e Processi.md

2. Primitive di I/O disponibili:

L’unica possibilità che gli abbiamo lasciato è quella di usare una primitiva, nella nostra macchina ad esempio abbiamo readconsole() e writeconsole().

Fonte: IO.md

Struttura delle primitive:

Dal file IO.md:

// Lettura di quanti byte in un buffer, nella periferica id
extern "C" void read_n(natl id, char* buf, natq quanti);

// Scrittura di quanti byte in un buffer, nella periferica id
extern "C" void write_n(natl id, const char* buf, natq quanti);

3. Meccanismo di chiamata delle primitive:

Chiamata dall’utente:

Dal file IO.md:

; Utente.s
.global read_n
read_n:
    int $IO_TIPO_RN  ; Chiamata di sistema tramite interruzione software
    ret

Gestione nel sistema:

; Sistema.s
.global a_read_n
.extern c_read_n
a_read_n:
    call c_read_n    ; Non salva/carica stato per efficienza
    iretq

Non effettuiamo salva_stato/carica_stato poiché faccaamo girare il driver nel contesto del processo attualmente in esecuzione.

4. Implementazione delle primitive:

Gestione concorrenza e sincronizzazione:

Dal file IO.md:

extern "C" void c_read_n(natl id, natb *buf, natl quanti){
    des_io *d = &array_des_io[id];

    sem_wait(d->mutex);     // Garantisce mutua esclusione

    // Trasferisce informazioni al descrittore
    d->buf = buf;
    d->quanti = quanti;

    // Abilita le interruzioni sulla periferica
    outputb(1, d->iCTL);

    // Blocca il processo in attesa del completamento
    sem_wait(d->sync);

    sem_signal(d->mutex);   // Rilascia mutua esclusione
}

5. Gestione attraverso driver e processi esterni:

Architettura driver:

L’operazione nel suo complesso ha quindi due attori:

Fonte: IO.md

Modulo I/O separato:

Per risolvere invece il secondo punto “trasformiamo” il driver in un processo in un nuovo modulo, chiamato modulo I/O. Il modulo I/O è un modulo indipendente, così come sistema e utente.

Fonte: IO.md

6. Protezione e verifica dati utente:

Principio di non fiducia:

Lo standard che assumiamo è quello di non fidarci dell’utente. Sarà quindi necessario controllare e approvare i dati che l’utente ci fornisce, in particolare il buffer dove salvare i dati, che ci è restituito attraverso un’indirizzo.

Fonte: IO.md

Controlli di sicurezza:

  1. Verifica che l’indirizzo sia normalizzato
  2. Verifica che l’indirizzo sia mappato nel processo
  3. Controllo accessi in scrittura per i buffer
  4. Prevenzione wrap-around degli indirizzi
  5. Verifica che tutto sia nella memoria condivisa

Vantaggi dell’approccio protetto:

  1. Sicurezza: Prevenzione di accessi non autorizzati alle periferiche
  2. Stabilità: Evita che processi utente corrompano il sistema
  3. Controllo centralizzato: Gestione coordinata delle risorse hardware
  4. Isolamento: Separazione tra processi e sistema operativo
  5. Robustezza: Gestione degli errori controllata dal kernel

Flusso completo di una operazione I/O:

  1. Processo utente chiama primitiva tramite INT
  2. Sistema passa a livello privilegiato
  3. Primitiva valida parametri e attiva periferica
  4. Processo viene bloccato su semaforo
  5. Interruzione hardware segnala completamento
  6. Driver processa i dati e risveglia processo
  7. Controllo torna al processo utente

Questo meccanismo garantisce che l’accesso alle periferiche avvenga sempre sotto il controllo del sistema operativo, mantenendo la sicurezza e l’integrità del sistema.

Domanda 12.2

Domanda: Descriva l’I/O con primitiva di sistema. Come funziona la primitiva di lettura da interfaccia?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 12.3

Domanda: Come funziona il driver e chi lo chiama nel sistema di I/O?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 12.4 (answered)

Domanda: Com’è collegato il modulo I/O con il resto del sistema?

Risposta: Il modulo I/O è collegato al resto del sistema attraverso un’architettura sofisticata che integra separazione modulare, comunicazione tramite primitive e gestione coordinata delle interruzioni, garantendo isolamento e funzionalità avanzate.

Architettura modulare del sistema:

Dal file IO.md:

Il modulo I/O è un modulo indipendente, così come sistema e utente. Come utente, anch’egli può affidarsi sulle funzioni di sistema, come se fosse un’altra via per accedervi.

Struttura dei tre moduli:

Dal file Sistemi Multiprocesso e Processi.md:

Il sistema che realizzeremo è organizzato in tre moduli:

Entrambi questi due moduli vengono eseguiti con il processore a livello sistema, in un contesto privilegiato, mentre utente verrà eseguito al livello utente.

1. Separazione fisica e mappatura in memoria:

Compilazione separata:

Nella nostra implementazione, i file che contengono il codice di questo modulo si trovano nella cartella io/ e sono io.cpp e io.s. Una volta compilati e collegati produrranno il file build/io che verrà caricato in memoria durante l’avvio del sistema e mappato nello spazio di indirizzamento di ogni processo, nella sezione IO/condivisa.

Fonte: IO.md

Memoria virtuale separata:

Dal log di avvio del sistema Sistemi Multiprocesso e Processi.md:

19 | [INF] - Suddivisione della memoria virtuale:
20 | [INF] - - sis/cond [ 0, 8000000000)
21 | [INF] - - sis/priv [ 8000000000, 10000000000)
22 | [INF] - - io /cond [ 10000000000, 18000000000)
23 | [INF] - - usr/cond [ffff800000000000, ffffc00000000000)

Mappatura del modulo I/O:

25 | [INF] - mappo il modulo I/O:
26 | [INF] - - segmento sistema read-only mappato a [ 10000000000, 1000000f000)
27 | [INF] - - segmento sistema read/write mappato a [ 10000010000, 10000031000)
28 | [INF] - - heap: [ 10000031000, 10000131000)
29 | [INF] - - entry point: start [io.s:11]

2. Isolamento e protezione tramite collegamento:

Protezione accidentale:

Separando i due moduli (sistema e I/O) siamo in grado di intercettare errori involontari, come chiamate interne a salva/carica_stato o l’accesso a code processi, poiché sono dichiarate in un’altro modulo che il collegatore non associa.

Fonte: IO.md

Vantaggi dell’isolamento:

3. Comunicazione tramite primitive specializzate:

Primitive riservate al modulo I/O:

In I/O e in sistema devono essere inoltre caricate ulteriori primitive aggiuntive, dedicate esclusivamente a I/O, salvate nella tabella IDT con il bit DPL = LIV_SISTEMA.

Fonte: IO.md

Interfaccia utente:

Dal file IO.md:

I moduli utente e I/O permettono la non atomicità, che invece è obbligatoria nel modulo sistema. L’utente ha acesso alle primitive di sistema sia alle nuove primitive realizzate in I/O, accessibili sempre tramite INT.

4. Gestione dei processi esterni tramite activate_pe():

Meccanismo di attivazione:

Una delle primitive riservate al modulo I/O è la primitiva activate_pe(), che serve ad attivare un processo esterno. Questa primitiva ha gli stessi parametri della normale activate_p(), con l’aggiunta di un’ulteriore parametro irq corrispondente al numero del piedino dell’APIC da cui arriveranno le richieste al quale il processo dovrà rispondere.

Fonte: IO.md

Tabella di associazione:

In particolare I/O ha una tabella a_p con un entrata per ogni piedino dell’APIC (24 piedini → 24 entrate). La activate_pe(), dopo aver attivato un processo, inserirà il corrispondente des_proc nell’entrata opportuna di a_p invece che inserirlo in pronti.

Fonte: IO.md

5. Catena di collegamento IRQ → Tipo → Handler → Processo:

Implementazione completa:

Dal file IO.md:

// Creiamo il collegamento irq->tipo->handler->processo esterno

// irq->tipo (tramite l'APIC)
apic::set_VECT(irq, tipo);

// Associazione tipo->handler (tramite la IDT)
// Nota: in sistema.s abbiamo creato un handler diverso per ogni possibile irq.
// L'irq che passiamo a load_handler serve ad identificare l'handler che ci serve.
load_handler(tipo, irq);

// Associazione handler->processo esterno (tramite 'a_p')
a_p[irq] = p;

// Ora che tutti i collegamenti sono stati creati possiamo iniziare a ricevere
// interruzioni da irq.
// Smascheriamo dunque le richieste irq nell'APIC
apic::set_MIRQ(irq, false);

6. Gestione delle interruzioni attraverso handler standardizzati:

Struttura degli handler:

Dal file IO.md:

handler_i:
	; Salvo lo stato del processo che stava girando
	CALL salva_stato

	; Lo inserisco in cima alla coda pronti
	; Essendo quello attualmente in esecuzione avrà
	;  sicuramente la priorità più alta degli altri
	CALL inspronti

	; Equivalente di esecuzione = a_p[i]
	MOVq a_p+i*8, %rax
	MOVq %rax, esecuzione

	; Cedo il controllo al processo esterno
	CALL carica_stato
	IRETQ

7. Primitiva wfi() per la sincronizzazione:

Implementazione coordinata:

Dal file IO.md:

Modulo I/O (io.s):

.global wfi
wfi:
	INT $TIPO_WFI
	RET

Modulo Sistema (sistema.s):

; Primitiva di sistema wfi() (waiting_for_interrupt)
a_wfi:
	; Stato del processo esterno riferito sopra
	CALL salva_stato
	CALL apic_send_EOI

	; Non abbiamo certezza di chi riprenderà l'esecuzione
	; Infatti questa porzione viene eseguita con interruzioni
	; abilitate, perciò potrebbe esserci qualcun'altro diverso
	; dal processo inserito con la inspronti() in cima a 'pronti'
	CALL schedulatore
	CALL carica_stato
	RET

8. Processo di inizializzazione e avvio:

Sequenza di avvio coordinata:

Dal log Sistemi Multiprocesso e Processi.md:

42 | [INF] 1 Creo il processo main I/O
43 | [INF] 1 proc=2 entry=start [io.s:11](1024) prio=1278 liv=0
44 | [INF] 1 Attendo inizializzazione modulo I/O...
45 | [INF] 2 Heap del modulo I/O: 100000B [0x10000031000, 0x10000131000)
46 | [INF] 2 Inizializzo la console (kbd + vid)
47 | [INF] 2 estern=3 entry=estern_kbd(int) [io.cpp:168](0) prio=1104 (tipo=50) liv=0 irq=1

9. Livelli di privilegio e controllo accessi:

Scelta del livello di sistema:

Non avendo però a disposizione questo livello ideale siamo costretti a scenglierne uno tra i due che abbiamo a disposizione. I/O gira quindi a LIV_SISTEMA. Questa scelta deriva da tutta una serie di motivi, in particolare:

Fonte: IO.md

Gestione delle interruzioni:

Pur avendo LIV_SISTEMA, il modulo girerà a interruzioni abilitate così come il codice del modulo utente. Questo vale sia per il codice dei processi esterni sia per il codice delle nuove primitive interne. Eventuali problemi di mutua esclusione dovranno quindi essere risolti utilizzando i semafori del sistema.

Fonte: IO.md

10. Utilizzo pratico dei processi esterni:

Struttura dei processi I/O:

Dal file IO.md:

extern "C" processo_esterno(natl i){
	// Accedo al descrittore di una specifica interfaccia i
	// Non è necessario validarlo poiché viene dal modulo io stesso
	des_io* d = &array_des_io[i];

	// Vado in attesa fino alla prossima wait_for_interrupt
	// Senza mai terminare
	for(;;){
		// Corpo del Processo
		wfi();
	}
}

Riepilogo dell’architettura di collegamento:

Aspetto Meccanismo Scopo
Separazione fisica Moduli compilati separatamente Isolamento e modularità
Mappatura memoria Spazi virtuali dedicati Protezione e organizzazione
Comunicazione Primitive tramite IDT Interfaccia controllata
Gestione interruzioni Handler → Processi esterni Risposta asincrona agli eventi
Attivazione processi activate_pe() con tabella a_p Associazione IRQ → Processo
Sincronizzazione wfi() cross-modulo Coordinamento tra moduli
Privilegi LIV_SISTEMA con interruzioni abilitate Accesso hardware con responsività

Vantaggi del collegamento:

  1. Modularità: Ogni modulo ha responsabilità specifiche e ben definite
  2. Isolamento: Errori di un modulo non propagano automaticamente agli altri
  3. Flessibilità: Facile aggiungere nuove funzionalità I/O senza modificare il kernel
  4. Sicurezza: Controllo degli accessi tramite primitive dedicate
  5. Prestazioni: Handler leggeri e processi esterni specializzati
  6. Manutenibilità: Codice separato facilita debugging e aggiornamenti

Collegamento con il resto del corso:

Il modulo I/O rappresenta quindi un ponte architetturale tra il kernel di base e le periferiche, fornendo un’interfaccia controllata e modulare per l’accesso all’hardware mantenendo isolamento e sicurezza.

Domanda 12.5

Domanda: Come funziona la activate_pe()? Cosa fa la wfi()?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 12.6 (answered)

Domanda: Quali sono le differenze tra primitiva di sistema e driver, primitiva di I/O e handler?

Risposta: Le differenze tra questi componenti riflettono la separazione di responsabilità nell’architettura del sistema di I/O, dove ogni elemento ha un ruolo specifico nella gestione delle operazioni con le periferiche.

1. PRIMITIVA DI SISTEMA vs DRIVER

Primitiva di Sistema:

L’unica possibilità che gli abbiamo lasciato è quella di usare una primitiva, nella nostra macchina ad esempio abbiamo readconsole() e writeconsole().

Fonte: IO.md

Le primitive di sistema sono interfacce software che:

Driver:

Il driver ha il compito di trasferire effettivamente i byte e sbloccare il processo quando l’operazione si è conclusa.

Fonte: IO.md

I driver sono gestori hardware che:

Divisione delle responsabilità:

L’operazione nel suo complesso ha quindi due attori:

Fonte: IO.md

2. PRIMITIVA DI I/O vs HANDLER

Primitiva di I/O (es. read_n, write_n):

Dal file IO.md:

extern "C" void c_read_n(natl id, natb *buf, natl quanti){
    des_io *d = &array_des_io[id];

    sem_wait(d->mutex);     // Garantisce mutua esclusione

    // Trasferisce informazioni al descrittore
    d->buf = buf;
    d->quanti = quanti;

    // Abilita le interruzioni sulla periferica
    outputb(1, d->iCTL);

    // Blocca il processo in attesa del completamento
    sem_wait(d->sync);

    sem_signal(d->mutex);   // Rilascia mutua esclusione
}

Le primitive di I/O:

Handler (Interrupt Handler):

Dal file IO.md:

a_wfi:
	CALL salva_stato
	CALL apic_send_EOI  ; ← Invio EOI all'APIC

Gli handler sono routine di interruzione che:

3. ARCHITETTURA DEL MODULO I/O

Separazione architettuale:

Per risolvere invece il secondo punto “trasformiamo” il driver in un processo in un nuovo modulo, chiamato modulo I/O. Il modulo I/O è un modulo indipendente, così come sistema e utente.

Fonte: IO.md

Struttura del sistema:

Dal file IO.md:

// Associazione irq->tipo (tramite l'APIC)
apic::set_VECT(irq, tipo);
// Associazione tipo->handler (tramite la IDT)
gate_init(tipo, routine);
// Smascheriamo le richieste irq nell'APIC
apic::set_MIRQ(irq, false);

4. FLUSSO OPERATIVO COMPLETO

Chiamata da processo utente:

Dal file IO.md:

; Utente.s
.global read_n
read_n:
    int $IO_TIPO_RN  ; Chiamata primitiva tramite interruzione software
    ret

Gestione nel sistema:

; Sistema.s
.global a_read_n
.extern c_read_n
a_read_n:
    call c_read_n    ; Non salva/carica stato per efficienza
    iretq

Completamento tramite interruzione:

Dal file IO.md:

extern "C" void c_driver_con(){
    array_des_io[0].buf[quanti_letti] = char(inputb(array_des_io[0].iOUT));
    // ... gestione carattere ...
    
    quanti_letti++;
    if(quanti_letti == array_des_io[0].quanti) {
        // Operazione completata - risveglia processo
        quanti_letti = 0;
        sem_signal(array_des_io[0].sync);
    }
    
    apic_send_EOI();
}

5. RIEPILOGO COMPARATIVO

Componente Dove opera Ruolo principale Accesso hardware Gestione processi
Primitiva Sistema Modulo Sistema API uniforme, controllo accessi No Validazione, protezione
Driver Modulo I/O Interfaccia hardware diretta Sì (IN/OUT) No
Primitiva I/O Modulo Sistema Sincronizzazione, avvio I/O Tramite driver Blocca/sblocca processi
Handler Modulo I/O Gestione eventi asincroni Sì (ACK interrupt) Sblocca processi

6. ESEMPIO PRATICO: Lettura da Console

Sequenza completa:

  1. Processo utente chiama read_n() (primitiva di sistema)
  2. Primitiva I/O c_read_n() configura dispositivo e blocca processo
  3. Driver nel modulo I/O gestisce la comunicazione hardware
  4. Handler c_driver_con() gestisce le interruzioni e sblocca il processo

Coordinamento tramite semafori:

Nel nostro sistema, i processi del modulo I/O vengono bloccati tramite la primitiva wfi() (Wait For Interrupt), che sospende il processo fino al verificarsi della corrispondente interruzione.

Fonte: IO.md

Approfondimenti:

Conclusioni: La distinzione tra questi componenti riflette i principi fondamentali dell’architettura moderna:

Domanda 12.7

Domanda: Come viene gestita la differenza tra Bus Mastering e le primitive di I/O tradizionali?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 12.8

Domanda: Descriva il processo di configurazione e inizializzazione del sistema I/O all’avvio.

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 12.9

Domanda: Come viene gestita la sincronizzazione tra processi e operazioni di I/O?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 12.10 (answered)

Domanda: Quali sono i vantaggi e gli svantaggi dell’approccio con driver separati?

Risposta: L’approccio con driver separati in un modulo I/O dedicato rappresenta un’evoluzione architettuale che risolve problemi fondamentali dei driver tradizionali, pur introducendo nuove complessità.

Problemi dell’approccio tradizionale:

Dal file IO.md:

La gestione con il meccanismo dei driver che abbiamo visto, per quanto funzionante, è però poco flessibile ed efficiente per due motivi:

  1. Il driver deve essere eseguito con interruzioni disabilitate, in quanto manipola direttamente le code processi
  2. Il driver non si può bloccare, in quanto non è un processo

VANTAGGI dell’approccio con driver separati:

1. Gestione delle interruzioni migliorata:

Il primo punto può causare problemi, in quanto costringe anche le interruzioni a priorità maggiore ad aspettare l’esecuzione prima di poter agire.

Fonte: IO.md

Soluzione con modulo separato:

Tramite questa soluzione risolviamo anche il problema delle interruzioni disabilitate, poiché, essendo adesso un processo come gli altri, basterà disattivarle utilizzando cli e sti solo nei punti dove si accede effettivamente alle strutture dati condivise.

Fonte: IO.md

Vantaggi:

2. Capacità di blocking I/O:

Problema driver tradizionale:

Il driver non si può bloccare, in quanto non è un processo

Fonte: IO.md

Soluzione:

Per risolvere invece il secondo punto “trasformiamo” il driver in un processo in un nuovo modulo, chiamato modulo I/O.

Fonte: IO.md

Vantaggi:

3. Isolamento e sicurezza:

Separazione moduli:

Separando i due moduli (sistema e I/O) siamo in grado di intercettare errori involontari, come chiamate interne a salva/carica_stato o l’accesso a code processi, poiché sono dichiarate in un’altro modulo che il collegatore non associa.

Fonte: IO.md

Vantaggi:

4. Architettura modulare:

Dal file IO.md:

Più precisamente, facciamo in modo che l’interruzione non mandi in esecuzione l’intero driver, ma solo un piccolo handler che ha come scopo mandare in esecuzione il processo, chiamato processo esterno, che si preoccuperà di svolgere le istruzioni che prima erano svolte dal driver.

Vantaggi:

5. Flessibilità nella gestione:

Gestione delle primitive:

In I/O e in sistema devono essere inoltre caricate ulteriori primitive aggiuntive, dedicate esclusivamente a I/O, salvate nella tabella IDT con il bit DPL = LIV_SISTEMA.

Fonte: IO.md

Vantaggi:

SVANTAGGI dell’approccio con driver separati:

1. Complessità implementativa:

Questa soluzione, per quanto utilizzata in sistemi reali, comporta grandi complicazione nella scrittura del codice.

Fonte: IO.md

Problemi:

2. Gestione dei livelli di privilegio:

Compromesso necessario:

Idealmente vorremmo che il codice contenuto in questo nuovo modulo girasse ad un livello intermedio tra LIV_UTENTE e LIV_SISTEMA in quanto:

Fonte: IO.md

Problemi:

3. Gestione della concorrenza:

Problemi di mutua esclusione:

Eventuali problemi di mutua esclusione dovranno quindi essere risolti utilizzando i semafori del sistema.

Fonte: IO.md

Problemi:

4. Overhead di context switching:

Costi aggiuntivi:

5. Verifica e validazione dati:

Problemi di sicurezza:

Lo standard che assumiamo è quello di non fidarci dell’utente. Sarà quindi necessario controllare e approvare i dati che l’utente ci fornisce, in particolare il buffer dove salvare i dati, che ci è restituito attraverso un’indirizzo.

Fonte: IO.md

Problemi:

RIEPILOGO COMPARATIVO:

Aspetto Driver Tradizionali Driver Separati
Interruzioni Sempre disabilitate Disabilitate solo se necessario
Blocking I/O Non supportato Completamente supportato
Isolamento Nessuno Moderato tramite linking
Complessità Bassa Alta
Sicurezza Rischio corruzione sistema Protezione parziale
Performance Handler veloci Overhead context switching
Manutenibilità Difficile Migliore modularità
Scalabilità Limitata Buona

Conclusioni:

L’approccio con driver separati rappresenta un compromesso architetturale che:

Pro:

Contro:

Approfondimenti:

Domanda 12.11

Domanda: Come viene garantita la protezione nell’accesso alle periferiche tramite il sistema di I/O?

Risposta: [La risposta verrà aggiunta quando richiesta]

13. DMA (Direct Memory Access)

Domanda 13.1 (answered)

Domanda: Cos’è il DMA e quali vantaggi offre rispetto al controllo di programma e alle interruzioni?

Risposta: Il DMA (Direct Memory Access) è una modalità di trasferimento dati che permette ai dispositivi di scambiare informazioni direttamente con la memoria RAM senza coinvolgere la CPU, eliminando l’overhead delle modalità tradizionali.

Definizione e Meccanismo:

Dal file DMA.md:

La modalità DMA (Direct Memory Access) prevede invece che sia direttamente il dispositivo ad eseguire le operazioni di lettura o scrittura necessarie sulla RAM, senza coinvolgere la CPU.

Il dispositivo DMA deve essere dotato di:

Confronto con Modalità Tradizionali:

Dal file DMA.md:

1. Controllo di Programma:

A “controllo di programma”: più veloce per quanto riguarda il trasferimento stesso, ma blocca la CPU per tutta la durata temporale tra il primo trasferimento e l’ultimo

2. Interruzioni:

Tramite Interruzioni: più lento, ma permette di utilizzare la CPU per eseguire altri processi durante le attese tra un trasferimento e l’altro

3. DMA:

Per entrambe le modalità è previsto il coinvolgimento della CPU, che dovrà eseguire prima una lettura e poi una scrittura, comportando due scambi dati sul bus

Protocollo HOLD/HOLDA (“Cycle Stealing”):

Dal file DMA.md:

Il coordinamento tra CPU e DMA avviene tramite handshake:

  1. Richiesta: Il dispositivo attiva HOLD quando vuole trasferire
  2. Cessione: La CPU termina l’operazione corrente, mette i piedini in alta impedenza e attiva HOLDA
  3. Trasferimento: Il dispositivo attiva i suoi piedini ed esegue il trasferimento
  4. Rilascio: Il dispositivo disattiva HOLD e rimette le uscite in alta impedenza
  5. Ripresa: La CPU disattiva HOLDA e riprende il normale funzionamento

In pratica, la CPU si mette in attesa dando la precedenza al DMA nell’accesso al bus. Questa tecnica è chiamata “cycle stealing”, in quanto il DMA “ruba” cicli di bus alla CPU.

Vantaggi del DMA:

Dal file DMA.md:

Il meccanismo resta vantaggioso in tre scenari principali:

  1. Se la CPU è più lenta della RAM (storico - home computer anni ‘80)
  2. Se il trasferimento a controllo di programma non è abbastanza veloce per il dispositivo
  3. Se il dispositivo deve trasferire i dati con più urgenza di quanto permesso dal meccanismo delle interruzioni

Esempio Moderno:

Gli ultimi due scenari possono verificarsi anche oggi, basta pensare ad alcune schede di rete che possono ricevere o inviare decine di milioni di pacchetti al secondo a velocità di 200 Gbps.

Vantaggi con Cache:

Dal file DMA.md:

Se inseriamo la cache […] viene introdotto un grande vantaggio: La CPU, statisticamente, può ora eseguire più istruzioni. Infatti parte delle istruzioni in memoria saranno probabilmente salvate proprio in cache e non richiederanno un accesso alla RAM.

Riepilogo Comparativo:

Modalità Coinvolgimento CPU Velocità Overhead Adatto per
Controllo Programma Completo Alto per singolo trasf. Blocca CPU Piccoli trasferimenti
Interruzioni Per ogni byte Basso Context switch Trasferimenti sporadici
DMA Solo setup iniziale Massimo Minimo Grandi volumi di dati

Il DMA rappresenta quindi la soluzione ottimale per trasferimenti di grandi quantità di dati, liberando la CPU per altre attività e massimizzando l’efficienza del sistema.

Domanda 13.2

Domanda: Cosa sono lo snooping e lo snarfing nella gestione della cache con DMA?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 13.3 (answered)

Domanda: Come interagisce il DMA con la MMU? Quali problemi sorgono con la memoria virtuale?

Risposta: L’interazione tra DMA e MMU presenta sfide fondamentali nell’architettura moderna, poiché il DMA opera esclusivamente su indirizzi fisici mentre il software utilizza indirizzi virtuali. Questa separazione crea problemi complessi che richiedono soluzioni sofisticate.

Problema fondamentale:

Dal file DMA.md:

La DMA può utilizzare soltanto indirizzi fisici, infatti non interagisce con la MMU. Tuttavia il software utilizza soltanto indirizzi virtuali [b, b+n).

Questa separazione genera un disallineamento architetturale che deve essere gestito dal sistema operativo.

Accorgimenti necessari per l’integrazione:

Dal file DMA.md:

Sono quindi necessari i seguenti accorgimenti per integrare DMA e MMU:

  1. Al DMA andrà comunicato l’indirizzo fisico f(b) e non quello virtuale b
  2. Se l’intervallo [b, b+n) attraversa più pagine non tradotte in frame contigui, il trasferimento deve essere spezzato in più trasferimenti in modo che ciascuno di essi coinvolga solo frame contigui.
  3. La traduzione degli indirizzi coinvolti in un trasferimento non deve cambiare mentre il trasferimento è in corso

1. Problema della traduzione degli indirizzi:

Conseguenze dell’uso diretto degli indirizzi virtuali:

Considerando il punto 1., comunicando b il DMA lo utilizzerebbe come fisico, accedendo a parti di memoria che non centrano niente con il buffer (tranne nei rari casi dove b = f(b)).

Fonte: DMA.md

Soluzione: Il sistema operativo deve:

2. Problema dei buffer discontigui:

Scenario problematico:

Per il punto 2. […] Se comunicassimo f(b) ed n, il DMA scriverà su [f(b), f(b) + n), invadendo F2 con effetti disastrosi. Quello che vogliamo noi è invece l’intervallo fisico [f(b), f(b+n)).

Fonte: DMA.md

Causa del problema: In memoria virtuale, pagine consecutive (Pag1, Pag3) possono essere mappate su frame fisici non contigui (F1, F3), con F2 appartenente a un altro processo.

Soluzione - Spezzamento del trasferimento:

Per poterlo modificare opportunamente il trasferimento, in questo caso, deve essere spezzato in due parti:

Implementazione pratica con PRD:

Dal file DMA.md:

char* tmp = vv;
while(totali > 0){
    f = trasforma(tmp);                    // Converte in indirizzo fisico
    
    if(tmp & 0x1){
        flog(ERROR_LOG, "indirizzo fisico di una pagina di vv dispari");
        return 0;
    }
    
    // g = primo indirizzo della pagina successiva  
    g = limit(f);
    
    // Dimensione della porzione da trasferire
    rimanenti = g - f;
    
    if(rimanenti > totali){
        rimanenti = totali;
    }
    
    // Configura PRD per questa porzione
    outputl(f, c->iBMPTR);
    outputl(rimanenti, c->iBMLEN);
    outputl(1, c->iCMD);
    
    tmp = g;
    totali -= rimanenti;
}

3. Problema dello swapping e della coerenza temporale:

Scenario critico con memoria virtuale:

Per il punto 3. immaginando quindi di trovarci in un sistema multiprocesso che realizzi swap-in/out dei processi per poter eseguire più processi di quanti ne possano entrare in RAM. Supponiamo quindi che un processo P1 avvii un trasferimento in DMA attraverso un buffer privato. È quindi necessario che P1 non venga mai swappato, altrimenti in quegli indirizzi subentrerebbe un processo P2 che vedrebbe la sua memoria privata modificata.

Fonte: DMA.md

Soluzioni per il problema dello swapping:

1. Pinning delle pagine in memoria:

2. Gestione dello stato del processo:

Problemi aggiuntivi con la memoria virtuale:

1. Frammentazione fisica:

2. Protezione e isolamento:

3. Sincronizzazione con la cache: Le operazioni DMA possono causare problemi di coerenza:

Architettura di soluzione moderna:

IOMMU (I/O Memory Management Unit): Nei sistemi moderni si utilizza una IOMMU che:

Vantaggi della soluzione IOMMU:

  1. Sicurezza: Dispositivi non possono accedere arbitrariamente alla memoria
  2. Semplificazione: Driver non devono gestire manualmente la traduzione
  3. Flessibilità: Supporto per buffer non contigui senza complessità aggiuntiva
  4. Compatibilità: Dispositivi legacy funzionano con memoria virtuale moderna

Approfondimenti:

Domanda 13.4 (answered)

Domanda: Cos’è il PCI Bus Mastering? Come funziona l’arbitraggio tra più dispositivi?

Risposta: Il PCI Bus Mastering è una tecnica che permette ai dispositivi collegati al bus PCI di diventare “master” del bus e di effettuare trasferimenti di dati direttamente tra loro e la memoria, senza coinvolgere il processore. Questo meccanismo è fondamentale per implementare il DMA (Direct Memory Access) su architetture moderne.

Definizione e concetto base:

Dal file DMA.md:

Un dispositivo con capacità di Bus Mastering può diventare temporaneamente master del bus e controllare i trasferimenti dati, liberando la CPU da queste operazioni intensive.

Caratteristiche fondamentali:

I dispositivi PCI dotati di capacità Bus Master possono generare autonomamente gli indirizzi di memoria e controllare il bus durante i trasferimenti, trasferendo dati direttamente tra periferica e memoria.

Fonte: DMA.md

Benefici prestazionali:

Meccanismo di Arbitraggio:

Il PCI Arbiter gestisce l’accesso al bus quando più dispositivi Bus Master competono simultaneamente.

Dal file DMA.md:

Il PCI Arbiter è il componente hardware che gestisce l’accesso al bus quando più dispositivi Bus Master competono per utilizzarlo simultaneamente attraverso segnali REQ# e GNT#.

Protocollo di arbitraggio:

  1. Richiesta: Ogni dispositivo Bus Master attiva il segnale REQ# (Request)
  2. Arbitraggio: Il PCI Arbiter esamina le richieste e decide quale autorizzare
  3. Concessione: L’arbiter attiva il segnale GNT# (Grant) per il dispositivo selezionato
  4. Accesso: Il dispositivo autorizzato diventa master e inizia i trasferimenti
  5. Rilascio: Al termine, il dispositivo rilascia il controllo del bus

Fonte: DMA.md

Politiche di arbitraggio supportate:

Implementazione Pratica: Esempio ATA Bus Mastering

Dal file DMA.md:

Identificazione del ponte:

bool bm::find(natb& bus, natb& dev, natb& fun) {
    natb code[] = { 0xff, 0x01, 0x01 };
    // Cerca dispositivo con Class Code 0x0101 (IDE controller)
    // con bit 7 = 1 (Bus Master capable)
}

Dobbiamo innanzitutto trovare il ponte tra i dispositivi PCI installati. Dalle specifiche ricaviamo che i primi due byte del Class Code del ponte devono valere 0x0101.

Fonte: DMA.md

Registri del Bus Master:

Dal file DMA.md:

Le specifiche ci dicono inoltre che l’indirizzo base dei registri del ponte è controllato dalla BAR, che si trova all’offset 36. I registri si trovano nello spazio di I/O agli offset 0, 2 e 4 rispetto alla base.

Sequenza operativa completa:

Dal file DMA.md:

// 1. Preparazione tabella PRD
prd[0] = reinterpret_cast<natq>(vv);
prd[1] = 0x80000000 | ((nn * 512) & 0xFFFF);

// 2. Configurazione ponte
bm::prepare(reinterpret_cast<natq>(prd), false);

// 3. Abilitazione interruzioni e avvio controllore
hd::enable_intr();
hd::start_cmd(lba, nn, READ_DMA);

// 4. Avvio Bus Master
bm::start();

// 5. Attesa completamento
while(!done);

Il resto del programma segue abbastanza da vicino lo schema suggerito nella sezione 3.1 delle specifiche: Prepara la tabella dei PRD, configura il ponte, programma il controllore dell’HD per il trasferimento in DMA, avvia il ponte ponendo a 1 lo Start Bit nel registro BMCCMD.

Fonte: DMA.md

Gestione delle Interruzioni:

Dal file DMA.md:

extern "C" void c_bmide(){
    done = true;
    bm::ack();
    hd::ack_intr();
    apic_send_EOI();
}

Al completamento del trasferimento DMA, il dispositivo genera un’interruzione hardware e il driver di interrupt viene invocato per gestire l’acknowledge sia del Bus Master che del controllore.

Fonte: DMA.md

Approfondimenti:

Domanda 13.5 (answered)

Domanda: Cosa sono i PRD (Physical Region Descriptors)? Come gestiscono buffer discontigui?

Risposta: I PRD (Physical Region Descriptors) sono strutture dati utilizzate dal sistema PCI Bus Mastering per descrivere regioni di memoria fisica dove trasferire i dati durante operazioni DMA. Permettono di gestire efficacemente buffer discontigui in memoria attraverso un meccanismo di scatter/gather.

Definizione e struttura:

Dal file DMA.md:

Per fornire informazioni sul buffer al controllore è necessario creare un PRD (Physical Region Descriptor) che ha la seguente forma:

La struttura PRD contiene:

Meccanismo scatter/gather:

L’interfaccia implementa un meccanismo di scatter/gather che permette il trasferimento di grandi blocchi che dovranno essere sparsi/raccolti dalla memoria, utilizzando di fatto buffer discontigui. Grazie a questo meccanismo è possibile diminuire il numero di interrupt al sistema.

Fonte: DMA.md

Gestione buffer discontigui:

I PRD risolvono il problema fondamentale dei buffer non contigui in memoria fisica, comune quando:

Registri del Bus Master IDE Controller:

Dal file DMA.md:

Offset Registro Funzione
0x00 Bus Master IDE Command Register Controllo operazioni
0x02 Bus Master IDE Status Register Stato trasferimento
0x04 - 0x07 Indirizzo tabella PRD Bus Master IDE Puntatore ai PRD

Implementazione pratica:

Dal file DMA.md:

// Preparazione della tabella PRD
prd[0] = reinterpret_cast<natq>(vv);                    // Indirizzo fisico buffer
prd[1] = 0x80000000 | ((nn * 512) & 0xFFFF);          // Dimensione + EOT bit

// Configurazione del ponte PCI
void bm::prepare(natq prd, bool write){
    outputl(prd, iBMDTPR);                              // Imposta puntatore PRD
    // ... configurazione direzione e stato
}

Processo di configurazione:

Dal file DMA.md:

Il resto del programma segue abbastanza da vicino lo schema suggerito nella sezione 3.1 delle specifiche:

  1. Prepara la tabella dei PRD
  2. Configura il ponte scrivendo l’indirizzo nel registro BMDTPR
  3. Programma il controllore HD per trasferimento DMA
  4. Avvia il ponte con lo Start Bit nel registro BMCCMD

Vincoli e limitazioni critiche:

Problema dei confini 64KiB:

Le regioni di memoria specificate tramite i PRD non devono trovarsi a cavallo dei confini di 64KiB.

Fonte: DMA.md

Conseguenze della violazione:

Quello che accade se si attraversano questi confini può avere esiti disastrosi. Infatti, il sommatore del ponte PCI-ATA potrebbe essere di soli 16bit, e quindi, dato l’indirizzo 0x1122FFFF, passerà poi all’indirizzo 0x11220000 invece che a 0x11230000.

Soluzioni per buffer discontigui:

1. Allineamento del buffer:

// Allineamento a 64KB nel file assembly
.balign 65536
vv: .fill 65536, 1

2. Trasferimenti multipli: Dal file DMA.md:

char* tmp = vv;
while(totali > 0){
    f = trasforma(tmp);                    // Converte in indirizzo fisico
    
    // g = primo indirizzo della pagina successiva  
    g = limit(f);
    
    // Dimensione della porzione da trasferire
    rimanenti = g - f;
    
    if(rimanenti > totali){
        rimanenti = totali;
    }
    
    // Configura PRD per questa porzione
    outputl(f, c->iBMPTR);
    outputl(rimanenti, c->iBMLEN);
    outputl(1, c->iCMD);
    
    tmp = g;
    totali -= rimanenti;
}

Vantaggi dei PRD:

  1. Efficienza: Riduzione del numero di interruzioni per buffer frammentati
  2. Flessibilità: Gestione automatica di buffer non contigui
  3. Prestazioni: Trasferimenti DMA senza intervento CPU
  4. Scalabilità: Supporto per tabelle multiple di PRD

Integrazione con il sistema:

I PRD si integrano perfettamente con:

Approfondimenti:

Domanda 13.6 (answered)

Domanda: Quali sono i registri del Bus Master IDE Controller e come vengono programmati?

Risposta: Il Bus Master IDE Controller utilizza tre registri principali per gestire le operazioni DMA con dispositivi IDE/SATA. Questi registri sono mappati nello spazio di I/O e permettono il controllo completo delle operazioni di trasferimento dati.

Architettura e indirizzamento:

Dal file DMA.md:

La funzione bus master IDE utilizza 16Byte dello spazio di I/O, accessibili come Byte, Word o Dword.

Tabella registri disponibili:

Offset Registro Diritti
0x00 Bus Master IDE Command Register (Primario) R/W
0x02 Bus Master IDE Status Register (Primario) R/W, Clear
0x04 - 0x07 Descriptor Table Pointer Register (Primario) R/W
0x08 Bus Master IDE Command Register (Secondario) R/W
0x0A Bus Master IDE Status Register (Secondario) R/W, Clear
0x0C - 0x0F Descriptor Table Pointer Register (Secondario) R/W

1. Bus Master IDE Command Register (BMCMD)

Caratteristiche:

Struttura del registro:

Dal file DMA.md:

Bit Funzione
7:4 Riservati (restituiscono sempre 0)
3 Controllo lettura/scrittura: 0=lettura, 1=scrittura
2:1 Riservati (restituiscono sempre 0)
0 Avvia/Arresta Bus Master: 1=abilita, 0=disabilita

Programmazione:

// Configurazione direzione trasferimento e avvio
void bm::prepare(natq prd, bool write){
    natb work = inputb(iBMCMD);
    
    if(write)
        work &= ~0x8;          // Bit 3 = 0 per scrittura verso dispositivo
    else
        work |= 0x8;           // Bit 3 = 1 per lettura da dispositivo
        
    outputb(work, iBMCMD);     // Configura direzione
    // ...
}

// Avvio operazione Bus Master
void bm::start(){
    natb work = inputb(iBMCMD);
    work |= 1;                 // Bit 0 = 1 per avviare
    outputb(work, iBMCMD);
}

2. Bus Master IDE Status Register (BMSTR)

Caratteristiche:

Struttura del registro:

Dal file DMA.md:

Bit Funzione
7 Solo simplex: 0=canali simultanei, 1=un canale alla volta
6 Drive 1 DMA Capable: Drive 1 supporta DMA
5 Drive 0 DMA Capable: Drive 0 supporta DMA
4:3 Riservati (sempre 0)
2 Interrupt: Interruzione da dispositivo IDE (clear scrivendo 1)
1 Error: Errore nel trasferimento (clear scrivendo 1)
0 Bus Master Active: Bus Master attivo

Programmazione:

// Azzeramento bit di interrupt ed errore
void bm::prepare(natq prd, bool write){
    // ... configurazione comando ...
    
    natb work = inputb(iBMSTR);
    work |= 0x6;               // Azzera bit Interrupt (2) ed Error (1)
    outputb(work, iBMSTR);
}

// Acknowledge interrupt nel driver
void bm::ack() {
    natb work = inputb(iBMCMD);
    work &= 0xFE;              // Ferma Bus Master (bit 0 = 0)
    outputb(work, iBMCMD);
    inputb(iBMSTR);            // Lettura per acknowledge
}

3. Descriptor Table Pointer Register (BMDTPR)

Caratteristiche:

Struttura del registro:

Dal file DMA.md:

Bit Funzione
31:2 Indirizzo base della Descriptor Table
1:0 Riservati (devono essere 0)

Vincoli importanti:

La Descriptor Table deve essere allineata a Dword, e non deve superare il limite di 64KB in memoria.

Programmazione:

// Configurazione puntatore alla tabella PRD
void bm::prepare(natq prd, bool write){
    outputl(prd, iBMDTPR);     // Imposta indirizzo tabella PRD
    // ... resto della configurazione ...
}

// Esempio di preparazione tabella PRD
natl prd[2];
prd[0] = reinterpret_cast<natq>(buffer_fisico);           // Indirizzo fisico
prd[1] = 0x80000000 | (dimensione & 0xFFFF);             // Dimensione + EOT bit

Processo di inizializzazione completo:

Dal file DMA.md:

1. Identificazione del controller:

// Cerca dispositivo PCI con Class Code 0x0101 (IDE controller)
bool bm::find(natb& bus, natb& dev, natb& fun) {
    natb code[] = { 0xff, 0x01, 0x01 };
    // Ricerca controller IDE con Bus Master capability (bit 7 = 1)
}

2. Inizializzazione registri:

void bm::init(natb bus, natb dev, natb fun) {
    // Lettura BAR all'offset 0x20 per indirizzo base registri
    natl base = pci::read_confl(bus, dev, fun, 0x20);
    base &= ~0x1;              // Azzera bit LSB (spazio I/O)
    
    // Calcolo indirizzi registri
    iBMCMD  = (ioaddr)(base + 0x00);
    iBMSTR  = (ioaddr)(base + 0x02);
    iBMDTPR = (ioaddr)(base + 0x04);
    
    // Abilitazione Bus Master nel registro Command PCI
    natw cmd = pci::read_confw(bus, dev, fun, 4);
    pci::write_confw(bus, dev, fun, 4, cmd | 0x5);  // Bit 0 (I/O) + bit 2 (Bus Master)
}

3. Sequenza operativa completa:

// 1. Preparazione tabella PRD
prd[0] = indirizzo_fisico_buffer;
prd[1] = 0x80000000 | dimensione_trasferimento;

// 2. Configurazione Bus Master
bm::prepare(reinterpret_cast<natq>(prd), false);  // false = lettura

// 3. Programmazione controller HD
hd::enable_intr();
hd::start_cmd(lba, settori, READ_DMA);

// 4. Avvio Bus Master
bm::start();

// 5. Attesa completamento (interrupt-driven)
while(!done);

Gestione interruzioni:

extern "C" void c_bmide(){
    done = true;           // Segnala completamento
    bm::ack();            // Acknowledge Bus Master
    hd::ack_intr();       // Acknowledge controller HD
    apic_send_EOI();      // End Of Interrupt all'APIC
}

Considerazioni pratiche:

  1. Sincronizzazione: I registri devono essere programmati in sequenza specifica
  2. Interrupt handling: Necessario gestire sia Bus Master che controller HD
  3. Allineamento: Buffer e PRD devono rispettare vincoli di allineamento
  4. Error handling: Controllo bit di errore nel registro di stato

Approfondimenti:

Domanda 13.7 (answered)

Domanda: Spieghi l’interazione tra DMA e cache. Quali problemi sorgono con le politiche write-through e write-back e come vengono risolti nei processori Intel e ARM?

Risposta: L’interazione tra DMA e cache presenta sfide significative per la coerenza dei dati, poiché il DMA accede direttamente alla RAM bypassando la cache della CPU.

Problemi principali:

Questi problemi nascono dal fatto che le operazioni del DMA potrebbero coinvolgere parti di RAM che erano state precedentemente copiate in cache.

Fonte: DMA.md

Politica Write-Through: Con la politica write-through, dal file DMA.md:

Soluzione Hardware (Intel):

Nei processori Intel la soluzione è risolta in hardware. Si fa in modo che il controllore cache osservi tutte le possibili sorgenti di scritture in RAM attraverso il bus condiviso, processo chiamato di snooping.

Se le linee di controllo identificano un operazione di scrittura, il controllore può usare il contenuto delle linee di indirizzo per eseguire una normale ricerca in cache, e nel caso di hit invalidare in autonomia la corrispondente cacheline.

Soluzione Software (ARM):

Nei sistemi ARM il problema è invece delegato al software, tramite istruzioni dedicate che permettono alla CPU di interagire direttamente con il controllore cache e invalidarne le cacheline. Il software dovrà quindi eseguire tutte le istruzioni specificando l’intervallo [b, b+n) (allineato opportunamente alle cacheline) subito dopo che il trasferimento sia terminato.

Politica Write-Back:

In questa politica le scritture della CPU vengono mantenute soltanto in cache e effettuate in maniera sincrona in secondi momenti. Questa politica comporta un problema sia nelle operazioni di uscita su DMA, poiché il buffer di lettura in RAM potrebbe contenere memoria non aggiornata.

Fonte: DMA.md

Esempio pratico - Gestione letture DMA:

Per risolvere possiamo utilizzare la tecinca di snooping, ma in questo caso il controllore cache deve implementare lo snarfing per le cacheline dirty.

Fonte: DMA.md

Differenze principali:

14. Architettura Moderna CPU

Domanda 14.1 (answered)

Domanda: Descriva le dipendenze sui dati e sui nomi nell’esecuzione delle istruzioni. Come vengono gestite?

Risposta: Le dipendenze nell’esecuzione delle istruzioni sono vincoli che impediscono di riordinare liberamente le istruzioni per mantenere la correttezza semantica del programma. Nell’architettura moderna delle CPU sono fondamentali per l’esecuzione fuori ordine.

Classificazione delle dipendenze:

Affinché il risultato finale dei registri sia significativo, dobbiamo rispettare una serie di condizioni chiamate Dipendenze, che si dividono in tre tipi:

Le dipendenze sono proprietà del programma, indipendenti dal circuito che esegue il programma.

Fonte: Architettura Moderna CPU Intel.md

1. Dipendenze sui Dati (Data Dependencies)

Definizione:

Un’istruzione i dipende dai dati di un’altra istruzione j, precedente ad essa, se i utilizza come uno dei registri src il registro dst di j.

Esempio:

ADD R1, R2, R3
; ...
SUB R3, R4, R5  ; R3 dipende dal risultato della ADD

Caratteristiche:

Le Dipendenze sui Dati forzano le istruzioni dipendenti a non poter essere riordinate liberamente, poiché è necessario che l’istruzione i venga eseguita dopo j, per avere il contenuto corretto del registro che dovrà utilizzare.

2. Dipendenze sui Nomi (Name Dependencies)

Le dipendenze sui nomi si dividono in due categorie:

A) Antidipendenze (WAR - Write After Read):

Un’istruizone i si dice antidipendente da un’altra istruzione j, successiva ad essa, se i utilizza come src lo stesso registro dst di j.

Esempio:

ADD R1, R2, R3    ; Legge R1
; ...
SUB R4, R5, R1    ; Scrive R1 - antidipendenza

B) Dipendenze in uscita (WAW - Write After Write):

Un’istruzione i si dice dipendente in uscita rispetto ad un’altra j, se entrambe vogliono scrivere nello stesso registro dst.

Esempio:

ADD R1, R2, R3    ; Scrive R3
; ...
SUB R4, R5, R3    ; Scrive R3 - dipendenza in uscita

Gestione delle dipendenze: Dal file Architettura Moderna CPU Intel.md:

1. Gestione dipendenze sui dati:

Per risolvere questo tipo di dipendenze, facciamo in modo che l’emissione setti il bit W del registro dst dell’istruzione che sta emettendo.

La stazione di emissione, prima di inviare i dati alla ALU, valuterà il bit W dei sorgenti, inviandoli solamente quando dst->W == 0.

2. Gestione dipendenze sui nomi:

Un modo per risolvere le dipendenze sui nomi è far andare in stallo l’emissione. Questa può infatti entrare e uscire liberamente dallo stato di stallo, tramite dei controlli.

Controlli specifici:

3. Rinomina dei registri (Register Renaming):

Per quanto riguarda le dipendenze sui nomi, esse sono anche chiamate dipendenze fittizie, questo perché se andiamo a sovrascrivere il contenuto di un registro è perché adesso lo vogliamo utilizzare per fare altro.

Possiamo quindi risolverle in questo modo:

Implementazione con registri logici e fisici:

Un modo per semplificare questo passaggio è inserire, prima degli $n$ registri fisici Fi, una tabella contentente $m$ registri logici Ri che punteranno ai registri fisici non in uso.

In questa nuova architettura, le istruzioni tradotte dalla decode faranno riferimento ai registri logici.

L’emissione si preoccuperà quindi anche di tradurli in registri fisici Fi con l’accortezza che: Il dst di una operazione deve sempre essere un registro fisico attualmente non puntato da nessun altro e non utilizzato dalla ALU (W == 0 && Count == 0).

Vantaggi del sistema: La gestione efficace delle dipendenze permette:

Questo sistema è alla base delle moderne CPU Intel e permette di ottenere prestazioni elevate mantenendo la correttezza semantica dei programmi.

Domanda 14.2 (answered)

Domanda: Come si risolvono le dipendenze sul controllo nell’architettura moderna?

Risposta: Le dipendenze sul controllo rappresentano una delle sfide più complesse nell’architettura moderna dei processori, poiché determinano quale codice deve essere eseguito in base al risultato di istruzioni di salto condizionato. La loro risoluzione richiede tecniche sofisticate che combinano predizione dei salti ed esecuzione speculativa.

Definizione delle dipendenze sul controllo:

Un istruzione i è dipendente dal controllo di una istruzione j, precedente ad essa, se j potrebbe comportare un salto che produrrà un flusso non definito a priori del programma.

Fonte: Architettura Moderna CPU Intel.md

Esempio di dipendenze sul controllo:

    CMP ;...
    JE fine1

    ADD ;...        # Sono Dipendenti sul Controllo della JE
    SUB ;...        # Sono Dipendenti sul Controllo della JE
    JMP fine2
fine1:
    DIV ;...        # È dipendente sul controllo della JE a causa di JMP fine2
fine2:
    MUL ;...        # In maniera raffinata questa non è dipendente

1. Predizione dei Salti (Branch Prediction)

Approccio base - Predizione statica:

Al primo salto il processore segue regole statiche per indovinare dove andrà a finire:

Fonte: Architettura Moderna CPU Intel.md

Predizione dinamica - Contatori di saturazione:

Per rendere questo processo dinamico salviamo in una struttura dati tutta una serie di informazioni relative ai salti già eseguiti. Le istruzioni di salto già avvenute cercano quindi di capire l’esito del salto riutilizzando questi dati, ricordando quando e dove siamo saltati e quando invece siamo “andati dritti”.

Fonte: Architettura Moderna CPU Intel.md

Sempre dal file Architettura Moderna CPU Intel.md:

Il contatore è un circuito a quattro stati:

Regole di funzionamento:

2. Branch Target Buffer (BTB)

In generale tutte queste cose vengono fatte dal Branch Target Buffer (BTB), a tutti gli effetti una cache, che: Ha come scopo associare ad ogni salto il proprio esito e la destinazione del salto (se avviene)

Fonte: Architettura Moderna CPU Intel.md

Caratteristiche del BTB:

L’operatore di prelievo si baserà quindi proprio sul contenuto di BTB per scegliere da dove recuperare i dati dopo aver riconosciuto un istruzione di salto.

Il BTB non si preoccupa delle colllisioni come avviene con la cache di memoria, poiché un suo errore non porta a effetti disastrosi ma “solamente” degli step della pipeline.

Predittori avanzati:

Predittori migliori ricordano anche la storia del salto, associando uno sheet register contenente una sequenza di bit che rappresentano lo storico dei salti effettuati (1) e non (0). Da questa informazione il predittore cerca quindi di imparare a utilizzarlo, cercando di trovare pattern.

3. Esecuzione Speculativa

Principio base:

Per quanto riguarda le dipendenze sul controllo anche qui, come per la pipeline, continuiamo a esaminare le informazioni come se il flusso dei dati fosse corretto. Infatti la Fetch & Decode ha continuato a prelevare istruzioni dal punto indicato nel BTB, supponendo di aver effettuato una predizione corretta.

In questo caso la nostra architettura andrà a eseguire queste istruzioni predette prima di sapere se debbano o meno essere eseguite. Questa tecnica si chiama Speculazione.

Fonte: Architettura Moderna CPU Intel.md

4. ReOrder Buffer (ROB)

Struttura e funzione:

Per un’implementazione corretta della specuazione è necessaria una nuova struttura dati chiamata ReOrder Buffer ROB. Questa struttura dati è una coda che ricostruisce l’ordine di emissione delle istruzioni. Al suo interno ha un bit T che, se settato, indica che l’operazione associata è terminata.

In questa nuova architettura, le istruzioni vanno a scrivere i risultati nei registri solo dopo che sono state ritirate dal ROB.

Gestione degli errori di predizione:

Adesso, quando terminiamo un’istruzione di Jcond e ne conosciamo l’esito, setteremo il suo bit T e la estraemo. Successivamente, valutandone l’esito:

Finché le istruzioni del ROB non sono prelevate non abbiamo infatti effetti sui registri veri e propri, perciò possiamo tranquillamente eseguire codice che non siamo sicuri vada eseguito.

5. Registri Speculativi e Non-Speculativi

Architettura duale:

Modifichiamo quindi gli indirizzi logici, in modo che invece di avere un solo indirizzo logico per ogni registro, ne conserviamo adesso due:

Recupero dagli errori:

In questo modo, quando svuotiamo il ROB nel caso delle Jcond che non hanno l’esito atteso, è sufficente copiare i valori non speculativi nei registri speculativi. Così facendo, alla prossima operazione, prelevando dal registro non speculativo, non avremo effetti collaterali poiché quelli salvati sono valori certi.

6. Alternative Semplici

Approccio conservativo:

Se non vogliamo implementare la “raffinatezza”, possiamo creare una dipendenza sul controllo nel momento in cui viene emessa una Jcond che genera uno stallo finché non si recupera il risultato.

Fonte: Architettura Moderna CPU Intel.md

Questo approccio è più semplice ma meno efficiente, poiché ferma completamente l’esecuzione in attesa del risultato del salto.

Approfondimenti:

Conclusione: La risoluzione delle dipendenze sul controllo rappresenta un equilibrio tra prestazioni e complessità. L’architettura moderna privilegia l’esecuzione speculativa con predizione dinamica, accettando il costo del recupero dagli errori per massimizzare il throughput delle istruzioni.

Domanda 14.3 (answered)

Domanda: Spieghi l’esecuzione speculativa e out of order con diagrammi. Come funziona la pipeline?

Risposta: L’esecuzione speculativa e out-of-order rappresenta l’evoluzione moderna dell’architettura delle CPU Intel, permettendo di superare i limiti sequenziali del codice assemblato per massimizzare il throughput delle istruzioni.

1. Pipeline Tradizionale - Fondamenti

Struttura base della pipeline:

Le istruzioni passeranno adesso in diverse fasi:

  1. Prelievo
  2. Decodifica
  3. Prelevio Operandi (dalla memoria o dai registri)
  4. Esecuzione dell’istruzione
  5. Scrittura del risultato nella destinazione

Fonte: Architettura Moderna CPU Intel.md

Diagramma pipeline base:

Tempo Prelievo Decodifica Prelevio Operandi Esecuzione Scrittura
t₀ i        
t₁ i+1 i      
t₂ i+2 i+1 i    
t₃ i+3 i+2 i+1 i  
t₄ i+4 i+3 i+2 i+1 i

In questo modo moltiplichiamo il numero di istruzioni completate al secondo per 5, ovvero il numero di stadi nella pipeline.

Problemi - ALEE (Hazards):

All’interno del flusso delle istruzioni ci sono alcune situazioni che ci impediscono di eseguire un’istruzione ad ogni ciclo di clock. Queste situazioni prendono il nome di ALEE.

Ne esistono di tre tipi:

Fonte: Architettura Moderna CPU Intel.md

2. Architettura Intel Moderna - Esecuzione Out-of-Order

Principio base:

Prendere le istruzioni CISC e tradurle internamente in istruzioni RISC.

Fonte: Architettura Moderna CPU Intel.md

Fetch & Decode avanzate:

Il circuito di Fetch ha al suo interno due buffer da 16Byte l’uno. Sono due poiché, per via delle dimensioni variabili delle operazioni CISC, non sappiamo nemmeno dove l’operazione inizi.

Il circuito di Decode si divide invece in due fasi:

  1. Fase di predecodifica: questa fase è necessaria a capire dove si trovano le istruzioni
  2. Fase di decodifica: si occupa di decodificare le istruzioni recuperate dalla Fetch per tradurle in microistruzioni RISC.

Architettura di esecuzione fuori ordine:

  FETCH & DECODE
       ↓
   EMISSIONE ← [Registri interni con campi W,C]
       ↓
   ┌─────────────────────────────────┐
   │    Stazioni di Prenotazione     │
   ├─────────┬─────────┬─────────────┤
   │  ALU 1  │  ALU 2  │   ALU n     │
   └─────────┴─────────┴─────────────┘
       ↓          ↓          ↓
      BUS (risultati verso registri)

Per ottenere questo risultato immaginiamo di avere più di un’unica ALU, ognuna preceduta da quelle che chiamiamo stazioni di prenotazione. Questo componente riceve le istruzioni dalla decode e le smisterà nelle varie stazioni di prenotazione passando attraverso i registri interni, diversi da quelli utilizzabili dal programmatore e che, oltre ai dati stessi, contengono anche due campi aggiuntivi:

Fonte: Architettura Moderna CPU Intel.md

3. Gestione delle Dipendenze

Classificazione:

Affinché il risultato finale dei registri sia significativo, dobbiamo rispettare una serie di condizioni chiamate Dipendenze, che si dividono in tre tipi:

Le dipendenze sono proprietà del programma, indipendenti dal circuito che esegue il programma.

A) Dipendenze sui Dati (RAW - Read After Write):

Un’istruzione i dipende dai dati di un’altra istruzione j, precedente ad essa, se i utilizza come uno dei registri src il registro dst di j.

Esempio:

ADD R1, R2, R3    ; j scrive R3
SUB R3, R4, R5    ; i legge R3 - dipendenza sui dati

Risoluzione:

Per risolvere questo tipo di dipendenze, facciamo in modo che l’emissione setti il bit W del registro dst dell’istruzione che sta emettendo. La stazione di emissione, prima di inviare i dati alla ALU, valuterà il bit W dei sorgenti, inviandoli solamente quando dst->W == 0.

B) Dipendenze sui Nomi:

Antidipendenze (WAR - Write After Read):

ADD R1, R2, R3    ; i legge R1
SUB R4, R5, R1    ; j scrive R1 - antidipendenza

Dipendenze in uscita (WAW - Write After Write):

ADD R1, R2, R3    ; i scrive R3
SUB R4, R5, R3    ; j scrive R3 - dipendenza in uscita

Risoluzione - Register Renaming:

Per quanto riguarda le dipendenze sui nomi, esse sono anche chiamate dipendenze fittizie, questo perché se andiamo a sovrascrivere il contenuto di un registro è perché adesso lo vogliamo utilizzare per fare altro.

Un modo per semplificare questo passaggio è inserire, prima degli $n$ registri fisici Fi, una tabella contentente $m$ registri logici Ri che punteranno ai registri fisici non in uso.

Traduzione Logico → Fisico:

Registri Logici → Tabella di Rinomina → Registri Fisici
    R1    →           F6            →      F6
    R2    →           F2            →      F2  
    R3    →           F7            →      F7

4. Esecuzione Speculativa e Predizione dei Salti

Branch Target Buffer (BTB):

In generale tutte queste cose vengono fatte dal Branch Target Buffer (BTB), a tutti gli effetti una cache, che: Ha come scopo associare ad ogni salto il proprio esito e la destinazione del salto (se avviene)

Fonte: Architettura Moderna CPU Intel.md

Predittore a quattro stati:

SNT ←→ WNT ←→ WT ←→ ST
(Strongly Not Taken) → (Weakly Not Taken) → (Weakly Taken) → (Strongly Taken)

Principio dell’esecuzione speculativa:

Per quanto riguarda le dipendenze sul controllo anche qui, come per la pipeline, continuiamo a esaminare le informazioni come se il flusso dei dati fosse corretto. In questo caso la nostra architettura andrà a eseguire queste istruzioni predette prima di sapere se debbano o meno essere eseguite. Questa tecnica si chiama Speculazione.

Fonte: Architettura Moderna CPU Intel.md

5. ReOrder Buffer (ROB) - Cuore dell’Esecuzione Speculativa

Struttura e funzione:

Per un’implementazione corretta della specuazione è necessaria una nuova struttura dati chiamata ReOrder Buffer ROB. Questa struttura dati è una coda che ricostruisce l’ordine di emissione delle istruzioni. Al suo interno ha un bit T che, se settato, indica che l’operazione associata è terminata.

In questa nuova architettura, le istruzioni vanno a scrivere i risultati nei registri solo dopo che sono state ritirate dal ROB.

Diagramma architettura completa con ROB:

    FETCH & DECODE
         ↓
      EMISSIONE ← [Tabella Registri Logici]
         ↓
    ┌─────────────────────────────────┐
    │    Stazioni di Prenotazione     │     ┌─────────────┐
    ├─────────┬─────────┬─────────────┤  →  │     ROB     │
    │  ALU 1  │  ALU 2  │   ALU n     │     │ [T][OP][DST]│
    └─────────┴─────────┴─────────────┘     │ [T][OP][DST]│
         ↓          ↓          ↓             │ [T][OP][DST]│
        BUS (risultati speculativi)          └─────────────┘
                  ↓                               ↓
              Registri Speculativi    →    Registri Non-Speculativi

Gestione errori di predizione:

Adesso, quando terminiamo un’istruzione di Jcond e ne conosciamo l’esito, setteremo il suo bit T e la estraemo. Successivamente, valutandone l’esito:

Finché le istruzioni del ROB non sono prelevate non abbiamo infatti effetti sui registri veri e propri, perciò possiamo tranquillamente eseguire codice che non siamo sicuri vada eseguito.

6. Registri Speculativi vs Non-Speculativi

Architettura duale:

Modifichiamo quindi gli indirizzi logici, in modo che invece di avere un solo indirizzo logico per ogni registro, ne conserviamo adesso due:

Recupero dagli errori:

In questo modo, quando svuotiamo il ROB nel caso delle Jcond che non hanno l’esito atteso, è sufficente copiare i valori non speculativi nei registri speculativi. Così facendo, alla prossima operazione, prelevando dal registro non speculativo, non avremo effetti collaterali poiché quelli salvati sono valori certi.

7. Gestione LOAD e STORE Speculative

Store Buffer:

Questo si ottiene inserendo uno Store Buffer, una coda nella quale effettuiamo le scritture/letture durante l’esecuzione speculativa, senza quindi accedere direttamente in memoria. Copieremo i dati in memoria solamente quando l’istruzione verrà recuperata dal ROB.

Fonte: Architettura Moderna CPU Intel.md

Gestione eccezioni speculative:

Per evitare quindi che si possa generare un fault in questi casi, quello che facciamo è dedicare un’ulteriore bit fault all’interno del ROB. Adesso, l’eccezione verrà sollevata solamente quando l’istruzione con il bit settato viene prelevata.

8. Vantaggi dell’Architettura Moderna

Prestazioni:

In questa architettura l’esecuzione va in attesa solo per via di limiti fisici. Per migliorare le prestazioni è infatti sufficente aumentare i parametri fisici: le dimensioni del ROB, il numero di ALU e stazioni di controllo, il numero di registri, …

Esempio pratico: Dal file Architettura Moderna CPU Intel.md:

// Ciclo for indipendente - perfetto per esecuzione out-of-order
for(int i = 0; i < 100000; ++i){
    a[i] = v1[i] + v2[i];  // Ogni iterazione è indipendente
}

Ogni operazione effettuata nei vari cicli del for è indipendente dalle altre. Non abbiamo quindi nessun obbligo ad eseguirle nell’ordine che il programmatore desidera. Infatti, se avessimo sufficenti sommatori a disposizione, potremmo persino effettuarle tutte insieme in parallelo.

Conclusione: L’esecuzione speculativa e out-of-order rappresenta un equilibrio sofisticato tra prestazioni e complessità, permettendo alle CPU moderne di superare i limiti imposti dalle dipendenze del codice sequenziale mantenendo la correttezza semantica dei programmi.

Approfondimenti:

Domanda 14.4

Domanda: Cosa è il ROB (Reorder Buffer) e a cosa serve nell’esecuzione out-of-order?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 14.5

Domanda: Qual è la differenza tra registri logici e fisici nell’architettura moderna?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 14.6

Domanda: Parli delle pipeline nell’architettura moderna e dei loro vantaggi.

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 14.7

Domanda: Come vengono gestite le istruzioni LOAD e STORE nell’esecuzione speculativa?

Risposta: [La risposta verrà aggiunta quando richiesta]

Domanda 14.8

Domanda: Come funziona l’interazione tra esecuzione speculativa e cache nelle CPU moderne? Descriva i problemi di sicurezza legati alla speculazione (Meltdown, Spectre).

Risposta: [La risposta verrà aggiunta quando richiesta]